BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Bielak Halina (Maria Curie-Skłodowska University in Lublin, Poland), Powroźnik Kamil (Maria Curie-Skłodowska University in Lublin, Poland)
Tytuł
An efficient algorithm for the density Turán problem of some unicyclic graphs
Źródło
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 479 - 486, rys., bibliogr. 11 poz.
Słowa kluczowe
Grafy, Algorytmy, Analiza matematyczna
Graphs, Algorithms, Mathematical analysis
Uwagi
summ.
Abstrakt
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)
Pełny tekst
Pokaż
Bibliografia
Pokaż
  1. 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.
  2. Bollobás B., Extremal Graph Theory, Academic Press (1978).
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. Godsil C. D. and Royle G., Algebraic Graph Theory, Springer (2001), http://dx.doi.org/10.1007/978-1-4613-0163-9.
  8. Jin G., Complete subgraphs of r-partite graphs, Combin. Probab. Comput., 1 (1992), 241-250, http://dx.doi.org/10.1017/s0963548300000274.
  9. Nagy Z. L., A multipartite version of the Turán problem - density conditions and eigenvalues, The Electronic Journal of Combinatorics, 18 (2011), # P46.
  10. Turán P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48 (1941), 436-452.
  11. Yuster R., Independent transversal in r-partite graphs, Discrete Math., 176 (1997), 255-261, http://dx.doi.org/10.1016/s0012-365x(96)00300-7.
Cytowane przez
Pokaż
ISSN
2300-5963
Język
eng
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu