- 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
-
- 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), # P46.
- Turán P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48 (1941), 436-452.
- 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
- ISSN
- 2300-5963
- Język
- eng
