Results 1 to 10 of about 1,260 (164)
On the extremal function for graph minors [PDF]
Journal of Graph Theory, 2022 AbstractFor a graph , let , where means that is a minor of . We show that if has average degree , then where is an explicitly defined constant. This bound matches a corresponding lower bound shown to hold for almost all such by Norin, Reed, Wood and the first author.
Andrew Thomason
exaly +4 more sources
Extremal infinite graph theory
Discrete Mathematics, 2011 We survey various aspects of infinite extremal graph theory and prove several new results. The lead role play the parameters connectivity and degree. This includes the end degree. Many open problems are suggested.
Maya Stein
exaly +5 more sources
Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
Discrete Mathematics, 1974 AbstractThe main result of this paper is that for a special, but rather wide class of “sample graphs”, the extremal graphs, i.e. the graphs of n vertices without subgraphs isomorphic to the sample graph and having maximum number of edges under this condition, have very simple and symmetric structure.
M Simonovits
exaly +2 more sources
Extremal graph of super line graph operation via generalized Randić index
Ain Shams Engineering JournalGraph operations enable the modification and transformation of graphs, enhancing data representation as well as effectiveness in fields such as computer science, mathematics, and data analysis.
Hoor Ul Ain +4 more
doaj +3 more sources
Proceedings of the London Mathematical Society, 2020 We study the uniqueness of optimal solutions to extremal graph theory problems. Lovasz conjectured that every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints so that the resulting set is satisfied by an asymptotically unique graph.
Grzesik, Andrzej +2 more
openaire +6 more sources
On some interconnections between combinatorial optimization and extremal graph theory [PDF]
Yugoslav Journal of Operations Research, 2004 The uniting feature of combinatorial optimization and extremal graph theory is that in both areas one should find extrema of a function defined in most cases on a finite set.
Cvetković Dragoš M. +2 more
doaj +1 more source
Tight upper bound on the maximum anti-forcing numbers of graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 Let $G$ be a simple graph with a perfect matching. Deng and Zhang showed that the maximum anti-forcing number of $G$ is no more than the cyclomatic number.
Lingjuan Shi, Heping Zhang
doaj +1 more source
Capture-Time Extremal Cop-Win Graphs
Discussiones Mathematicae Graph Theory, 2021 We investigate extremal graphs related to the game of Cops and Robbers. We focus on graphs where a single cop can catch the robber; such graphs are called cop-win.
Offner David, Ojakian Kerry
doaj +1 more source
On the Boundary of Incidence Energy and Its Extremum Structure of Tricycle Graphs
Frontiers in Physics, 2020 With the wide application of graph theory in circuit layout, signal flow chart and power system, more and more attention has been paid to the network topology analysis method of graph theory.
Hongyan Lu, Zhongxun Zhu
doaj +1 more source
The Signless Laplacian Estrada Index of Unicyclic Graphs [PDF]
Mathematics Interdisciplinary Research, 2017 For a simple graph G, the signless Laplacian Estrada index is defined as SLEE(G)=∑ni=1eqi, where q1, q2,..., qn are the eigenvalues of the signless Laplacian matrix of G.
Hamid Reza Ellahi +3 more
doaj +1 more source