Results 11 to 20 of about 25,547 (250)
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
On some extremal problems in graph theory [PDF]
, 1999 In this paper we are concerned with various graph invariants (girth, diameter, expansion constants, eigenvalues of the Laplacian, tree number) and their analogs for weighted graphs -- weighing the graph changes a combinatorial problem to one in analysis. We study both weighted and unweighted graphs which are extremal for these invariants.
Dmitry Jakobson, Igor Rivin
openalex +3 more sources
Problems in extremal graph theory [PDF]
, 2010 We consider a variety of problems in extremal graph and set theory. The {\em chromatic number} of $G$, $\chi(G)$, is the smallest integer $k$ such that $G$ is $k$-colorable.
Lale Özkahya
openalex +2 more sources
Problems in extremal graphs and poset theory
, 2018 In this dissertation, we present three different research topics and results regarding such topics. We introduce partially ordered sets (posets) and study two types of problems concerning them-- forbidden subposet problems and induced-poset-saturation problems. We conclude by presenting results obtained from studying vertex-identifying codes in graphs.
Shanise Walker
openalex +5 more sources
EXTREMAL PROBLEMS IN GRAPH THEORY: A COMBINATORIAL OPTIMIZATION PERSPECTIVE
Advances and Applications in Discrete MathematicsThe extremal theory of graphs considers the study of how large or small a graph invariant may be, according to certain constraints. The field crosses the overlying with combinatorial optimization, in which optimal configurations are studied under ...
R. Thangathamizh +2 more
openalex +3 more sources
On a valence problem in extremal graph theory
Discrete Mathematics, 1973 Vorliegende Arbeit bezieht sich auf nicht-orientierte, Schlingen und mehrfache Kanten nicht enhaltende Graphen. Bezeichne \(L\) einen solchen vom vollständigen \(p\)-Graphen \(K_p\) verschiedenen \(p\)-chromatischen Graphen, welcher eine Kante \(e\) so enthält, daß \(L-e\) ein \((p-1)\)-chromatischer Graph ist. Als Hauptergebnis der vorliegenden Arbeit
P. Erdös, Miklós Simonovits
openalex +3 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
On a problem in extremal graph theory
Journal of Combinatorial Theory, Series B, 1977 From the authors introduction. Let \(G(n,m)\) denote a graph \((V,E)\) with \(n\) vertices and \(m\) edges and \(K_1\) a complete graph with \(i\) vertices. \textit{P.Turán} proved that every \(G(n,T(n,k))\) contains a \(K_k\), where \[ T(n,k) = \frac{k-2}{2(k-1)}(n^2-r^2)+\binom r2+1, \] \(r\equiv n(\mod k-1)\) and \(0\leq r\leq k-2\).
D.T Busolini, P. Erdös
openalex +2 more sources
An extremal problem for sets with applications to graph theory
Journal of Combinatorial Theory, Series A, 1985 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Noga Alon
openalex +2 more sources
A survey on spectral conditions for some extremal graph problems [PDF]
, 2021 This survey is two-fold. We first report new progress on the spectral extremal results on the Tur´an type problems in graph theory. More precisely, we shall summarize the spectral Tur´an function in terms of the adjacency spectral radius and the signless ...
Yongtao Li, Weijun Liu, Lihua Feng
semanticscholar +1 more source