✦ LIBER ✦

Multipartite Turán problem for connected graphs and hypergraphs

✍ Scribed by Zsolt Tuza

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 561 KB
Volume: 112
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90234-k

No coin nor oath required. For personal study only.

✦ Synopsis

Tuza, Z., Multipartite Turan problem for connected graphs and hypergraphs, Discrete Mathematics 112 (1993) 199-206. Giving a partial solution to a problem of Bialostocki and Dierker, we determine the maximum number of edges in a k-chromatic graph G with color classes of given cardinalities n,, , n,, such that each connected component of G has at most p vertices, p) n, + + nk. We also characterize the extremal graphs and investigate to what extent their properties remain valid when multipartite r-uniform hypergraphs are considered. Problem 1. Given n=(nl, . ...&), r, ~((n(=n~+ ... +&>p and k>,r), determine the maximum number t(n,p, r) of edges in a subhypergraph A? of K: such that every connected component of 2 has at most p vertices.

📜 SIMILAR VOLUMES

Turán problems for integer-weighted grap

Turán problems for integer-weighted graphs

✍ Zoltán Füredi; André Kündgen 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

## Abstract A multigraph is (__k__,__r__)‐dense if every __k__‐set spans at most __r__ edges. What is the maximum number of edges ex~ℕ~(__n__,__k__,__r__) in a (__k__,__r__)‐dense multigraph on __n__ vertices? We determine the maximum possible weight of such graphs for almost all __k__ and __r__ (e

Turán's theorem and k-connected graphs

✍ Nicolas Bougard; Gwenaël Joret 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract The minimum size of a __k__‐connected graph with given order and stability number is investigated. If no connectivity is required, the answer is given by Turán's Theorem. For connected graphs, the problem has been solved recently independently by Christophe et al., and by Gitler and Val

A Turán type problem for interval graphs

✍ Harvey Abbott; Meir Katchalski 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 313 KB

We consider the following analogue of a problem of Turin for interval graphs: Let c = c(n, rn) be the largest integer such that any interval graph with n vertices and at least m edges contains a complete subgraph on c vertices. We determine the value of c(n, m) explicitly.

Another extremal problem for Turan graph

Another extremal problem for Turan graphs

✍ Bruce Hedman 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 207 KB

We consider only finite, undirected graphs without loops or multiple edges. A clique of a graph G is a maximal complete subgraph of G. The clique number w(G) is the number of vertices in the largest clique of G. This note addresses the foflowing question: Which graphs G on n vertices with w(G) = r h

Label-connected graphs and the gossip pr

Label-connected graphs and the gossip problem

✍ F. Göbel; J.Orestes Cerdeira; H.J. Veldman 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 791 KB

Gobel, F., J. Orestes Cerdeira and H.J. Veldman, Label-connected graphs and the gossip problem, Discrete Mathematics 87 (1991) 29-40. A graph with m edges is called label-connected if the edges can be labeled with real numbers in such a way that, for every pair (u, v) of vertices, there is a (u, v)

Critical groups for complete multipartit

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

✍ Brian Jacobson; Andrew Niedermaier; Victor Reiner 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

## Abstract The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and compl