The spectral closeness of a graph G is defined as the spectral radius of the closeness matrix of G , whose ( u , v )-entry for vertex u and vertex v is 2 − d G ( u,v ) if u ≠ v and 0 otherwise, where d G ( u , v ) is the distance between u and v in G . The residual spectral closeness of a nontrivial graph G is defined as the minimum spectral closeness of the subgraphs of G with one vertex deleted. We propose local grafting operations that decrease or increase the spectral closeness and determine those graphs that uniquely minimize and/or maximize the spectral closeness in some families of graphs. We also discuss extremal properties of the residual spectral closeness.
An induced matching in a graph is a set of edges whose endpoints induce a $1$-regular subgraph. Gupta et al. (2012,\cite{Gupta}) showed that every $n$-vertex graph has at most $10^{\frac{n}{5}}\approx 1.5849^n$ maximal induced matchings, which is attained by the disjoint union of copies of the complete graph $K_5$. In this paper, we show that the maximum number of maximal and maximum induced matchings in a connected graph of order $n$ is \begin{align*} \begin{cases} {n\choose 2} &~ {\rm if}~ 1\leq n\le 8; \\ {{\lfloor \frac{n}{2} \rfloor}\choose 2}\cdot {{\lceil \frac{n}{2} \rceil}\choose 2} -(\lfloor \frac{n}{2} \rfloor-1)\cdot (\lceil \frac{n}{2} \rceil-1)+1 &~ {\rm if}~ 9\leq n\le 13; \\ 10^{\frac{n-1}{5}}+\frac{n+144}{30}\cdot 6^{\frac{n-6}{5}} &~ {\rm if}~ 14\leq n\le 30;\\ 10^{\frac{n-1}{5}}+\frac{n-1}{5}\cdot 6^{\frac{n-6}{5}} & ~ {\rm if}~ n\geq 31, \\ \end{cases} \end{align*} and also show that this bound is tight. This result implies that we can enumerate all maximal induced matchings of an $n$-vertex connected graph in time $O(1.5849^n)$. Moreover, our result provides an estimate on the number of maximal dissociation sets of an $n$-vertex connected graph.
For a graph G with vertex set V ( G ) and u , v ∈ V ( G ), the distance between vertices u and v in G , denoted by d G ( u , v ), is the length of a shortest path connecting them and it is ∞ if there is no such a path, and the closeness of vertex u in G is c G (u) = ∑ w ∈ V ( G ) 2- d G (u,w) . Given a graph G that is not necessarily connected, for u , v ∈ V ( G ), the closeness matrix of G is the matrix whose ( u , v )-entry is equal to 2 - d G (u,v) if u ≠ v and 0 otherwise, the closeness Laplacian is the matrix whose ( u , v )-entry is equal to $$ \left\{\begin{array}{c}-{2}^{-{d}_G(u,v)}\hspace{1em}\mathrm{if}\enspace u\ne v,\enspace \\ \enspace {c}_G(u)\hspace{1em}\hspace{1em}\mathrm{otherwise}\hspace{0.5em}\end{array}\right.\hspace{0.5em} $$ and the closeness signless Laplacian is the matrix whose ( u , v )-entry is equal to $$ \left\{\begin{array}{c}{2}^{-{d}_G(u,v)}\hspace{1em}\hspace{1em}\&\mathrm{if}\enspace \mathrm{u}\ne \mathrm{v},\\ {c}_G(u)\hspace{1em}\hspace{1em}\mathrm{otherwise}.\end{array}\right. $$ We establish relations connecting the spectral properties of closeness Laplacian and closeness signless Laplacian and the structural properties of graphs. We give tight upper bounds for all nontrivial closeness Laplacian eigenvalues and characterize the extremal graphs, and determine all trees and unicyclic graphs that maximize the second smallest closeness Laplacian eigenvalue. Also, we give tight upper bounds for the closeness signless Laplacian eigenvalues and determine the trees whose largest closeness signless Laplacian eigenvalues achieve the first two largest values.
The generalized distance spectral radius of a connected graph $G$ is the spectral radius of the generalized distance matrix of $G$, defined by $$D_α(G)=αTr(G)+(1-α)D(G), \;\;0\leα\le 1,$$ where $D(G)$ and $Tr(G)$ denote the distance matrix and diagonal matrix of the vertex transmissions of $G$, respectively. This paper characterizes the unique graph with minimum generalized distance spectral radius among the connected graphs with fixed chromatic number, which answers a question about the generalized distance spectral radius in spectral extremal theories. In addition, we also determine graphs with minimum generalized distance spectral radius among the $n$-vertex trees and unicyclic graphs, respectively. These results generalize some known results about distance spectral radius and distance signless Laplacian spectral radius of graphs.
In tensor eigenvalue problems, one is likely to be more interested in H-eigenvalues of tensors. The largest H-eigenvalue of a nonnegative tensor or of a uniform hypergraph is the spectral radius of the tensor or of the uniform hypergraph. We find upper bounds and lower bounds (interlacing inequalities) for the largest H-eigenvalue of a principal subtensor of a symmetric zero diagonal tensor that is of even order or nonnegative, as well as lower bounds for the largest H-eigenvalue of a uniform hypergraph with some vertices or edges removed. We also investigate similar problems for the least H-eigenvalues. We give examples to verify the sharpness of the bounds or in some cases for uniform hypergraphs, we characterize the equality. Particularly, for a connected linear $k$-uniform hypergraph $G$ with $v\in V(G)$, we give a sharp lower bound for the spectral radius of $G-v$ in terms of the spectral radius of $G$ and the degree of $v$ and characterize the extremal hypergraphs, and show that the maximum spectral radius of the subhypergraphs with one vertex removed is greater than or equal to the spectral radius of the hypergraph minus one, which is attained if and only if it is a Steiner system $S(2,k,n)$.
Let [Formula: see text] be a simple graph of order [Formula: see text] with vertex set [Formula: see text] and edge set [Formula: see text]. The arithmetic–geometric matrix [Formula: see text] of [Formula: see text] is a matrix of order [Formula: see text] defined by [Formula: see text] if [Formula: see text] and 0 otherwise, where [Formula: see text] stands for the degree of the vertex [Formula: see text] in [Formula: see text]. The arithmetic–geometric characteristic polynomial of [Formula: see text] is the characteristic polynomial of [Formula: see text]. The arithmetic–geometric energy [Formula: see text] of [Formula: see text] is the sum of absolute values of all eigenvalues of [Formula: see text]. In this paper, we obtain the arithmetic–geometric characteristic polynomial and arithmetic–geometric energy of some specific graphs. In addition, we also consider the arithmetic–geometric characteristic polynomial and arithmetic–geometric energy change of these graphs when one edge is deleted.
The Pareto H-eigenvalues of nonnegative tensors and (adjacency tensors of) uniform hypergraphs are studied. Particularly, it is shown that the Pareto H-eigenvalues of a nonnegative tensor are just the spectral radii of its weakly irreducible principal subtensors, and those hypergraphs that minimize or maximize the second largest Pareto H-eigenvalue over several well-known classes of uniform hypergraphs are determined.
'/%3e%3cuse xlink:href='%23a' transform='rotate(23.036 .093 25.536)'/%3e%3cuse xlink:href='%23a' transform='rotate(45.87 1.273 16.18)'/%3e%3cuse xlink:href='%23a' transform='rotate(69.945 .996 12.078)'/%3e%3cuse xlink:href='%23a' transform='rotate(20.66 -19.689 31.932)'/%3e%3c/svg%3e)
