PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 5 | 563--571
Tytuł artykułu

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

Warianty tytułu
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
PL
EN
Rocznik
Tom
5
Strony
563--571
Opis fizyczny
Twórcy
  • Maria Curie-Skłodowska University in Lublin, Poland
  • 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),
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171422584

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.