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

• Autorzy: Halina Bielak , Kamil Powroźnik
• 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)

Słowa kluczowe

PL

Grafy; Algorytmy; Analiza matematyczna

EN

Graphs; Algorithms; Mathematical analysis

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 479-486

Twórcy

autor

Halina Bielak

• Maria Curie-Skłodowska University in Lublin, Poland

autor

Kamil Powroźnik

• 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),