Results 11 to 20 of about 34,683 (312)
An extremal problem in graph theory II [PDF]
Journal of the Australian Mathematical Society, 1980 AbstractWe contine our study of the following combinatorial problem: What is the largest integer N = N (t, m, p) for which there exists a set of N people satisfying the following conditions: (a) each person speaks t languages, (b) among any m people there are two who speak a common language and (c) at most p speak a common language.
H. L. Abbott, Meir Katchalski, A. C. Liu
openalex +3 more sources
Stateless Quantum Structures and Extremal Graph Theory [PDF]
Reports on Mathematical Physics, 2020 We study hypergraphs which represent finite quantum event structures. We contribute to results of graph theory, regarding bounds on the number of edges, given the number of vertices. We develop a missing one for 3-graphs of girth 4. As an application of the graph-theoretical approach to quantum structures, we show that the smallest orthoalgebra with an
Václav Voràček
openalex +3 more sources
Rational exponents in extremal graph theory [PDF]
Journal of the European Mathematical Society, 2018 Given a family of graphs \mathcal{H} , the extremal number ex (n, \mathcal{H}) is the largest m
Boris Bukh, David Conlon
openalex +6 more sources
It Is Better to Be Semi-Regular When You Have a Low Degree [PDF]
EntropyWe study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity as well as the full spectrum distribution. For an integer d∈3,7,
Theodore Kolokolnikov
doaj +2 more sources
Incidence bounds via extremal graph theory [PDF]
The study of counting point-hyperplane incidences in the $d$-dimensional space was initiated in the 1990's by Chazelle and became one of the central problems in discrete geometry. It has interesting connections to many other topics, such as additive combinatorics and theoretical computer science. Assuming a standard non-degeneracy condition, i.e., that
Aleksa Milojević +2 more
openalex +3 more sources
On tricyclic graphs with maximum atom–bond sum–connectivity index [PDF]
HeliyonThe sum-connectivity, Randić, and atom-bond connectivity indices have a prominent place among those topological indices that depend on the graph's vertex degrees.
Sadia Noureen +5 more
doaj +2 more sources
Three conjectures in extremal spectral graph theory [PDF]
Journal of Combinatorial Theory, Series B, 2017 We prove three conjectures regarding the maximization of spectral invariants over certain families of graphs. Our most difficult result is that the join of $P_2$ and $P_{n-2}$ is the unique graph of maximum spectral radius over all planar graphs. This was conjectured by Boots and Royle in 1991 and independently by Cao and Vince in 1993.
Michael Tait, Josh Tobin
openalex +4 more sources
Some new results in extremal graph theory [PDF]
, 2011 In recent years several classical results in extremal graph theory have been improved in a uniform way and their proofs have been simplified and streamlined. These results include a new Erd s-Stone-Bollob s theorem, several stability theorems, several saturation results and bounds for the number of graphs with large forbidden subgraphs.
Vladimir Nikiforov
openalex +4 more sources
Problems in extremal graph theory and Euclidean Ramsey theory
, 2019 This thesis addresses problems of three types. The first type is finding extremal numbers for unions of graphs, each with a colour-critical edge (joint work with V. Nikiforov). In 1968, Simonovits found extremal numbers $ex(n,H)$ for graphs with a colour-critical edge for large $n$ (without specifying how large).
Sergei Tsaturian
openalex +4 more sources
An extremal problem in graph theory [PDF]
Journal of the Australian Mathematical Society, 1970 G(n;l) will denote a graph of n vertices and l edges. Let f0(n, k) be the smallest integer such that there is a G (n;f0(n, k)) in which for every set of k vertices there is a vertex joined to each of these. Thus for example fo = 3 since in a triangle each pair of vertices is joined to a third.
P. Erdös, Leo Moser
openalex +2 more sources