PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 2 | 479--486
Tytuł artykułu

An efficient algorithm for the density Turán problem of some unicyclic graphs

Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let H = (V (H),E(H)) be a simple connected graph of order n with the vertex set V (H) and the edge set E(H). We consider a blow-up graph G[H]. We are interested in the following problem. We have to decide whether there exists a blow-up graph G[H], with edge densities satisfying special conditions (homogeneous or inhomogeneous), such that the graph H does not appear in a blow-up graph as a transversal. We study this problem for unicyclic graphs H with the cycle C3. We show an efficient algorithm to decide whether a given set of edge densities ensures the existence of H in the blow-up graph G[H].(original abstract)
Rocznik
Tom
2
Strony
479--486
Opis fizyczny
Twórcy
  • Maria Curie-Skłodowska University in Lublin, Poland
  • Maria Curie-Skłodowska University in Lublin, Poland
Bibliografia
  • Baber R., Johnson J. R. and Talbot J., The minimal density of triangles in tripartite graphs, LMS J. Comput. Math., 13 (2010), 388-413, http://dx.doi.org/10.1112/S1461157009000436.
  • Bollobás B., Extremal Graph Theory, Academic Press (1978).
  • Bondy A., Shen J., Thomassé S. and Thomassen C., Density Conditions for triangles in multipartite graphs, Combinatorica, 26 (2006), http://dx.doi.org/10.1007/s00493-006-0009-y.
  • Brown W. G., Erdös P. and Simonovits M., Extremal problems for directed graphs, Journal of Combinatorial Theory, Series B 15 (1) (1973), 77-93, http://dx.doi.org/10.1016/0095-8956(73)90034-8.
  • Csikvári P. and Nagy Z. L., The density Turán Problem, Combinatorics, Probability and Computing, 21 (2012), 531-553, http://dx.doi.org/10.1017/S0963548312000016.
  • Füredi Z., Turán type problems, Survey in Combinatorics Vol. 166 of London Math. Soc. Lecture Notes (A.D. Keedwell, ed.) (1991), 253-300, http://dx.doi.org/10.1017/cbo9780511666216.010.
  • Godsil C. D. and Royle G., Algebraic Graph Theory, Springer (2001), http://dx.doi.org/10.1007/978-1-4613-0163-9.
  • Jin G., Complete subgraphs of r-partite graphs, Combin. Probab. Comput., 1 (1992), 241-250, http://dx.doi.org/10.1017/s0963548300000274.
  • Nagy Z. L., A multipartite version of the Turán problem - density conditions and eigenvalues, The Electronic Journal of Combinatorics, 18 (2011),
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171327083

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.