Results 21 to 30 of about 999 (266)
Discrete Mathematics, 1999 The \(\alpha\)-weight of an edge \(xy\) of a graph \(G\) is \(d(x)^\alpha\cdot d(y)^\alpha\) where \(d(x)\) and \(d(y)\) are the degrees of the vertices \(x\) and \(y\). The \(\alpha\)-weight of \(G\) is the sum of the \(\alpha\)-weights of its edges. The authors establish the \(\alpha\)-weight of a graph with any fixed number of edges for \(\alpha=1\)
Béla Bollobás +2 more
openaire +2 more sources
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 0001, Matthew Wales
openaire +3 more sources
A Class of Fibonacci Matrices, Graphs, and Games
Mathematics, 2022 In this paper, we define a class of Fibonacci graphs as graphs whose adjacency matrices are obtained by alternating binary Fibonacci words. We show that Fibonacci graphs are close in size to Turán graphs and that their size-stability tradeoff defined as ...
Valentin E. Brimkov, Reneta P. Barneva
doaj +1 more source
Extremal Graph Realizations and Graph Laplacian Eigenvalues
SIAM Journal on Discrete Mathematics, 2023 For a regular polyhedron (or polygon) centered at the origin, the coordinates of the vertices are eigenvectors of the graph Laplacian for the skeleton of that polyhedron (or polygon) associated with the first (non-trivial) eigenvalue. In this paper, we generalize this relationship.
openaire +2 more sources
An Extremal Property of Turán Graphs [PDF]
The Electronic Journal of Combinatorics, 2010 Let ${\cal F}_{n,t_r(n)}$ denote the family of all graphs on $n$ vertices and $t_r(n)$ edges, where $t_r(n)$ is the number of edges in the Turán's graph $T_r(n)$ – the complete $r$-partite graph on $n$ vertices with partition sizes as equal as possible.
Felix Lazebnik, Spencer Tofts
openaire +2 more sources
Extremal graphs for edge blow-up of graphs [PDF]
Journal of Combinatorial Theory, Series B, 2022 Given a graph $H$ and an integer $p$, the {\it edge blow-up} of $H$, denoted as $H^{p+1}$, is the graph obtained from replacing each edge in $H$ by a clique of size $p+1$ where the new vertices of the cliques are all different. The Turán numbers for edge blow-up of matchings were first studied by Erdős and Moon.
openaire +2 more sources
The maximum number of $P_\ell$ copies in $P_k$-free graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Generalizing Tur\'an's classical extremal problem, Alon and Shikhelman investigated the problem of maximizing the number of $T$ copies in an $H$-free graph, for a pair of graphs $T$ and $H$.
Ervin Győri +3 more
doaj +1 more source
Ars Mathematica Contemporanea, 2012 A graph G is singular if the zero-one adjacency matrix has the eigenvalue zero. The multiplicity of the eigenvalue zero is called the nullity of G . For two vertices y and z of G , we call ( G , y , z ) a device with respect to y and z .
Irene Sciriha +4 more
openaire +2 more sources
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
Extremal problems of double stars [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 In a generalized Tur\'an problem, two graphs $H$ and $F$ are given and the question is the maximum number of copies of $H$ in an $F$-free graph of order $n$. In this paper, we study the number of double stars $S_{k,l}$ in triangle-free graphs.
Ervin Győri +2 more
doaj +1 more source