BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Author
Bielak Halina (Maria Curie-Skłodowska University in Lublin, Poland), Powroźnik Kamil (Maria Curie-Skłodowska University in Lublin, Poland)
Title
An efficient algorithm for the density Turán problem of some unicyclic graphs
Source
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 479 - 486, rys., bibliogr. 11 poz.
Keyword
Grafy, Algorytmy, Analiza matematyczna
Graphs, Algorithms, Mathematical analysis
Note
summ.
Abstract
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)
Full text
Show
Bibliography
Show
  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.
Cited by
Show
ISSN
2300-5963
Language
eng
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu