For a graph $G$ and a set $B\subseteq V(G)$, the spread $\mathrm{sp}(B)$ of $B$ is the difference between the largest and the smallest degree in $G$ of a vertex of $B$, and for an integer $k\geq0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\leq k$. Caro, Lauri and Zarb derived a lower bound for $\mathrm{sp}(G,k)$ and, among several families of graphs, considered \[ \mathrm{MOP}(n,k)=\min \{\mathrm{sp}(G,k):G\text{ is a maximal outerplanar graph of order }n\} \] and determined $\mathrm{MOP}(n,k)$ up to an additive constant for every $k\not =2,$ leaving the case $k=2$ open, with the bounds $4n/9\leq \mathrm{MOP}(n,2)\leq (5n+19)/11$. We first prove a lower bound on $\mathrm{sp}(G,k)$ for an arbitrary graph $G$ in terms of its order $n$, its number of edges $m$ and its minimum degree $\delta $. This lower bound contains the bounds of Caro, Lauri and Zarb and, for $k=0$, the bound $\mathrm{rep}(G)\geq \left\lceil n/(2d-2\delta +1)\right\rceil $ of Caro and West, where $d=2m/n$. We determine when this lower bound is attained, exhibit explicit graphs attaining it, and show that it is exact for all graphs once $n\geq n_{0}(\delta ,k,d)$. We then apply the bound to maximal outerplanar graphs: adjusting the count to this class we prove \[ \mathrm{MOP}(n,2)\geq \left\lceil \frac{4n+10}{9}\right\rceil \qquad \text{for every }n\geq 14, \] with equality for $n\equiv 2\ (\mathrm{mod}\ 18)$, and $\mathrm{MOP}(n,2)=4n/9+O(1)$ for every $n$.
Let $\lambda_1(G) \geq \dots \geq \lambda_n(G)$ be the adjacency spectrum of a graph $G$ on $n$ vertices. The spectral distance $\sigma(G,H)$ between $n$-vertex graphs $G$ and $H$ is the Manhattan distance between their spectra, i.e. $\sigma(G,H) = \sum_{i=1}^n |\lambda_i(G) - \lambda_i(H)|$. Given a set $\mathcal{G}$...
Irena M. Jovanović, Jelena Sedlar, R. Škrekovski· 0 citations
For a family $\mathcal{F}$ of $k$-graphs, $\ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $\ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n...
The power graph $\mathscr{P}(G)$ of a group $G$ is defined as the simple graph with vertex set $G$, and two distinct vertices $x$ and $y$ are joined by an edge if and only if either $x= y^k$ or $y= x^k$, $k \in \mathbb{N}$. In this paper, first, we obtain the characteristic polynomial of $\mathscr{P}(\mathbb{Z}_m \time...
Komal Kumari, P. Panigrahi· Journal of Algebra Combinato...· 0 citations
Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the su...
For a connected and non-complete graph $G$ of order $n$, its toughness is defined as \[ \tau(G)=\min\bigl\{|S|/c(G-S):S\subseteq V(G),\ c(G-S)>1\bigr\}, \] where $c(G-S)$ denotes the number of components of $G-S$. Let $\alpha(G)$ denote the independence number of $G$. An elementary bound on toughness is $$\tau(G)\leq\f...
Let $\mathbf{G}=\{G_1,\dots,G_{n}\}$ be a collection of not necessarily distinct $n$-vertex graphs with a common vertex set $V$. A cycle $C$ with $V(C)\subseteq V$ and $|E(C)|\leq n$ is called \emph{rainbow} in $\mathbf{G}$, if there exists an injection $\phi\colon E(C)\to [n]$ such that $e\in E(G_{\phi(e)})$ for each...