Dehmer et al. [Interrelations of graph distance measures based on topological indices, PLoS One 9 (2014) e94985] explored the graph measures based on some topological indices and demonstrated some useful …
Dehmer et al. [Interrelations of graph distance measures based on topological indices, PLoS One 9 (2014) e94985] explored the graph measures based on some topological indices and demonstrated some useful properties of them. In this work, we survey the graph measures based on the Balaban index of a graph, and prove some extremal properties on them for several classes of graphs. Moreover, through numerical calculation and comparison, we find the graph measures based on Balaban index of a graph behave better than that based on Randić index in some special cases.
A $k$-tree is a spanning tree in which every vertex has degree at most $k$. In this paper, we provide a sufficient condition for the existence of a $k$-tree in …
A $k$-tree is a spanning tree in which every vertex has degree at most $k$. In this paper, we provide a sufficient condition for the existence of a $k$-tree in a connected graph with fixed order in terms of the adjacency spectral radius and the signless Laplacian spectral radius, respectively. Also, we give a similar condition for the existence of a perfect matching in a balanced bipartite graph with fixed order and minimum degree.
Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G: The signless Laplacian Q(G) of G is defined as …
Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G: The signless Laplacian Q(G) of G is defined as Q(G):= A(G) +D(G). Cvetkovic called the study of the adjacency matrix the A-spectral theory, and the study of the signless Laplacian{the Q-spectral theory. To track the gradual change of A(G) into Q(G), in this paper it is suggested to study the convex linear combinations A_ (G) of A(G) and D(G) defined by A? (G) := ?D(G) + (1 - ?)A(G), 0 ? ? ? 1. This study sheds new light on A(G) and Q(G), and yields, in particular, a novel spectral Tur?n theorem. A number of open problems are discussed.
Let G be the set of simple graphs (or multigraphs) G such that for each G∈G there exists at least two non-empty disjoint proper subsets V1,V2⊆V(G) satisfying V(G)∖(V1∪V2)≠φ and edge …
Let G be the set of simple graphs (or multigraphs) G such that for each G∈G there exists at least two non-empty disjoint proper subsets V1,V2⊆V(G) satisfying V(G)∖(V1∪V2)≠φ and edge connectivity κ′(G)=e(Vi,V(G)∖Vi) for 1≤i≤2. A multigraph is a graph with possible multiple edges, but no loops. Let τ(G) be the maximum number of edge-disjoint spanning trees of a graph G. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of τ(G), we mainly give the relationship between the third largest (signless Laplacian) eigenvalue and the bounds of κ′(G) and τ(G) of a simple graph or a multigraph G∈G, respectively.
Let $r$ and $m$ be two integers such that $r\geq m$. Let $H$ be a graph with order $|H|$, size $e$ and maximum degree $r$ such that $2e\geq |H|r-m$. We …
Let $r$ and $m$ be two integers such that $r\geq m$. Let $H$ be a graph with order $|H|$, size $e$ and maximum degree $r$ such that $2e\geq |H|r-m$. We find a best lower bound on spectral radius of graph $H$ in terms of $m$ and $r$. Let $G$ be a connected $r$-regular graph of order $|G|$ and $ k < r$ be an integer. Using the previous results, we find some best upper bounds (in terms of $r$ and $k$) on the third largest eigenvalue that is sufficient to guarantee that $G$ has a $k$-factor when $k|G|$ is even. Moreover, we find a best bound on the second largest eigenvalue that is sufficient to guarantee that $G$ is $k$-critical when $k|G|$ is odd. Our results extend the work of Cioabă, Gregory and Haemers [J. Combin. Theory Ser. B, 1999] who obtained such results for 1-factors.
Abstract In this article, we obtain a sufficient condition for the existence of regular factors in a regular graph in terms of its third largest eigenvalue. We also determine all …
Abstract In this article, we obtain a sufficient condition for the existence of regular factors in a regular graph in terms of its third largest eigenvalue. We also determine all values of k such that every r ‐regular graph with the third largest eigenvalue at most has a k ‐factor.
The \emph{distance matrix} of a simple connected graph $G$ is $D(G)=(d_{ij})$, where $d_{ij}$ is the distance between the $i$th and $j$th vertices of $G$. The \emph{distance signless Laplacian matrix} of …
The \emph{distance matrix} of a simple connected graph $G$ is $D(G)=(d_{ij})$, where $d_{ij}$ is the distance between the $i$th and $j$th vertices of $G$. The \emph{distance signless Laplacian matrix} of the graph $G$ is $D_Q(G)=D(G)+Tr(G)$, where $Tr(G)$ is a diagonal matrix whose $i$th diagonal entry is the transmission of the vertex $i$ in $G$. In this paper, first, upper and lower bounds for the spectral radius of a nonnegative matrix are constructed. Applying this result, upper and lower bounds for the distance and distance signless Laplacian spectral radius of graphs are given, and the extremal graphs for these bounds are obtained. Also, upper bounds for the modulus of all distance (respectively, distance signless Laplacian) eigenvalues other than the distance (respectively, distance signless Laplacian) spectral radius of graphs are given. These bounds are probably first of their kind as the authors do not find in the literature any bound for these eigenvalues. Finally, for some classes of graphs, it is shown that all distance (respectively, distance signless Laplacian) eigenvalues other than the distance (respectively, distance signless Laplacian) spectral radius lie in the smallest Ger\^sgorin disc of the distance (respectively, distance signless Laplacian) matrix.
The toughness t(G) of a graph G=(V,E) is defined as t(G)=min|S| c(G-S), in which the minimum is taken over all S⊂V such that G-S is disconnected, where c(G-S) denotes the …
The toughness t(G) of a graph G=(V,E) is defined as t(G)=min|S| c(G-S), in which the minimum is taken over all S⊂V such that G-S is disconnected, where c(G-S) denotes the number of components of G-S. We present two tight lower bounds for t(G) in terms of the Laplacian eigenvalues and provide strong support for a conjecture for a better bound which, if true, implies both bounds, and improves and generalizes known bounds by Alon, Brouwer, and the first author. As applications, several new results on perfect matchings, factors and walks from Laplacian eigenvalues are obtained, which leads to a conjecture about Hamiltonicity and Laplacian eigenvalues.
The distance signless Laplacian spectral radius of a connected graph G is the spectral radius of the distance signless Laplacian matrix of G, defined as where is the diagonal matrix …
The distance signless Laplacian spectral radius of a connected graph G is the spectral radius of the distance signless Laplacian matrix of G, defined as where is the diagonal matrix of vertex transmissions of G and is the distance matrix of G. In this paper, we determine the graphs with minimum distance signless Laplacian spectral radius among the trees, unicyclic graphs and bipartite graphs with fixed numbers of vertices, respectively, and determine the graphs with minimum distance signless Laplacian spectral radius among the connected graphs with fixed numbers of vertices and pendant vertices, and the connected graphs with fixed number of vertices and connectivity, respectively.
The distance signless Laplacian spectral radius of a connected graph , denoted by , is the maximal eigenvalue of the distance signless Laplacian matrix of . In this paper, we …
The distance signless Laplacian spectral radius of a connected graph , denoted by , is the maximal eigenvalue of the distance signless Laplacian matrix of . In this paper, we find a sharp lower bound as well as a sharp upper bound of in terms of the clique number. Furthermore, both extremal graphs are uniquely determined.
In this paper, we derive interrelations of graph distance measures by means of inequalities. For this investigation we are using graph distance measures based on topological indices that have not …
In this paper, we derive interrelations of graph distance measures by means of inequalities. For this investigation we are using graph distance measures based on topological indices that have not been studied in this context. Specifically, we are using the well-known Wiener index, Randić index, eigenvalue-based quantities and graph entropies. In addition to this analysis, we present results from numerical studies exploring various properties of the measures and aspects of their quality. Our results could find application in chemoinformatics and computational biology where the structural investigation of chemical components and gene networks is currently of great interest.