The Density Turán Problem for Some 3-uniform Unihypercyclic Linear Hypergraphs. An Efficient Testing Algorithm

• Autorzy: Halina Bielak , Kamil Powroźnik
• Języki publikacji: EN

Abstrakty

EN

Let H = (V, E) be a 3-uniform linear hypergraph with one hypercycle C3. We consider a blow-up hypergraph B[H]. We are interested in the following problem. We have to decide whether there exists a blow-up hypergraph B[H] of the hypergraph H, with hyperedge densities satisfying special conditions, such that the hypergraph H appears in a blow-up hypergraph as a transversal. We present an efficient algorithm to decide whether a given set of hyperedge densities ensures the existence of a 3-uniform linear hypergraph H with hypercycle C3 in the blow-up hypergraph B[H]. Moreover, we state some relations between roots of the multivariate matching polynomial and the inhomogeneous density Turán problem. (original abstract)

Słowa kluczowe

EN

Graphs; Algorithms

PL

Grafy; Algorytmy

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 563--571

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

• ] R. Baber, J.R. Johnson and J. Talbot, The minimal density of triangles in tripartite graphs, LMS J. Comput. Math., 13 (2010), 388-413, http://dx.doi.org/10.1112/S1461157009000436.
• C. Berge, Graphs and hypergraphs, Elsevier, New York, NY, USA (1973).
• H. Bielak, K. Powroźnik, An efficient algorithm for the density Turán problem of some unicyclic graphs, Annals of Computer Science and Information Systems, Proceedings of the 2014 FedCSIS, Vol. 2 (2014), 479-486, http://dx.doi.org/10.15439/978-83-60810-58-3.
• H. Bielak, K. Powroźnik, An efficient algorithm for the density Turán problem of 3-uniform linear hypertrees, unpublished.
• B. Bollobás, Extremal Graph Theory, Academic Press (1978).
• A. Bondy, J. Shen, S. Thomassé and C. Thomassen, Density Conditions for triangles in multipartite graphs, Combinatorica, 26 (2006), http://dx.doi.org/10.1007/s00493-006-0009-y.
• W.G Brown, P. Erdös and M. Simonovits, 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.
• P. Csikvári and Z. L. Nagy, The density Turán Problem, Combinatorics, Probability and Computing, 21 (2012), 531-553, http://dx.doi.org/10.1017/S0963548312000016.
• Z. Füredi, 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.
• C.D. Godsil and G. Royle, Algebraic Graph Theory, Springer (2001), http://dx.doi.org/10.1007/978-1-4613-0163-9.
• G. Jin, Complete subgraphs of r-partite graphs, Combin. Probab. Comput., 1 (1992), 241-250, http://dx.doi.org/10.1017/s0963548300000274.
• Z.L. Nagy, A multipartite version of the Turán problem - density conditions and eigenvalues, The Electronic Journal of Combinatorics, 18 (2011),

Identyfikatory

DOI

10.15439/2015F260