For a graph G, let μ2(G) denote its second smallest Laplacian eigenvalue. It was conjectured that μ2(G)+μ2(G‾)≥1, where G‾ is the complement of G. This conjecture has been proved for various families ...of graphs. Here, we prove this conjecture in the general case. Also, we will show that max{μ2(G),μ2(G‾)}≥1−O(n−13), where n is the number of vertices of G.
Let G be a graph with adjacency matrix A(G) and the degree diagonal matrix D(G). For any real α∈0,1, the matrix Aα(G) of a graph is defined as Aα(G)=αD(G)+(1−α)A(G). Denote its eigenvalues by ...λ1(Aα(G))≥λ2(Aα(G))≥⋯≥λn(Aα(G)). In this paper, for 1/2<α<1, the Nordhaus-Gaddum type bound for the second largest Aα-eigenvalue of a graph is considered. We show that λ2(Aα(G))+λ2(Aα(G‾))≥nα−1, and the extremal graphs for which the equality holds are Kn and Sn. If G∉{Kn,Sn,Kn−e}, then λ2(Aα(G))+λ2(Aα(G‾))≥(n−1)α. Moreover, we give two upper Nordhaus-Gaddum type bounds for the second largest Aα-eigenvalue of a graph.
A seminal result by Nordhaus and Gaddum states that 2n≤χ(G)+χ(G¯)≤n+1 for every graph G of order n, where G¯ is the complement of G and χ is the chromatic number. We study similar inequalities for ...χg(G) and colg(G), which denote, respectively, the game chromatic number and the game coloring number of G. Those graph invariants give the score for, respectively, the coloring and marking games on G when both players use their best strategies.
Let G be a graph of order n, and let q1(G)≥q2(G)≥⋯≥qn(G) denote the signless Laplacian eigenvalues of G. Ashraf and Tayfeh-Rezaie (2014) 3 showed that q1(G)+q1(G‾)≤3n−4, with equality holding if and ...only if G or G‾ is the star K1,n−1. In this paper, we prove that q2(G)+q2(G‾)≤2n−4, where the equality holds if and only if G or G‾ is K2, P4 or C4. Also, we discuss the following problem: for n≥6, does q2(G)+q2(G‾)≤2n−5 always hold? We provide positive answers to this problem for the graphs with disconnected complements and the bipartite graphs, and determine the graphs attaining the bound. Moreover, we show that q2(G)+q2(G‾)≥n−2, and the extremal graphs are also characterized.
The unitary Cayley graph $\Gamma_n$ of a finite ring $\mathbb{Z}_n$ is the graph with vertex set $\mathbb{Z}_n$ and two vertices $x$ and $y$ are adjacent if and only if $x-y$ is a unit in ...$\mathbb{Z}_n$. A family $\mathcal{F}$ of mutually edge disjoint trees in $\Gamma_n$ is called a tree cover of $\Gamma_n$ if for each edge $e\in E(\Gamma_n)$, there exists a tree $T\in\mathcal{F}$ in which $e\in E(T)$. The minimum cardinality among tree covers of $\Gamma_n$ is called a tree covering number and denoted by $\tau(\Gamma_n)$. In this paper, we prove that, for a positive integer $ n\geq 3 $, the tree covering number of $ \Gamma_n $ is $ \displaystyle\frac{\varphi(n)}{2}+1 $ and the tree covering number of $ \overline{\Gamma}_n $ is at most $ n-p $ where $ p $ is the least prime divisor of $n$. Furthermore, we introduce the Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of rings $\mathbb{Z}_n$.
Let
G
be a simple, connected graph,
D
(
G
) be the distance matrix of
G
, and
Tr
(
G
) be the diagonal matrix of vertex transmissions of
G
. The distance signless Laplacian matrix of
G
is defined as
...D
Q
(
G
)
=
T
r
(
G
)
+
D
(
G
)
, and the distance signless Laplacian spectral radius of
G
is the largest eigenvalue of
D
Q
(
G
)
. In this paper, we study Nordhaus–Gaddum-type inequalities for distance signless Laplacian eigenvalues of graphs and present some new upper and lower bounds on the distance signless Laplacian spectral radius of
G
and of its line graph
L
(
G
), based on other graph-theoretic parameters, and characterize the extremal graphs. Further, we study the distance signless Laplacian spectrum of some graphs obtained by operations.
Let $G$ be a graph with $n$ vertices. We denote the largest signless Laplacian eigenvalue of $G$ by $q_1(G)$ and Laplacian eigenvalues of $G$ by $\mu_1(G)\ge\cdots\ge\mu_{n-1}(G)\ge\mu_n(G)=0$. It is ...a conjecture on Laplacian spread of graphs that $\mu_1(G)-\mu_{n-1}(G)\le n-1$ or equivalently $\mu_1(G)+\mu_1(\overline G)\le2n-1$. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph $G$, $\mu_1(G)\mu_1(\overline G)\le n(n-1)$. Aouchiche and Hansen Discrete Appl. Math. 2013 conjectured that $q_1(G)+q_1(\overline G)\le3n-4$ and $q_1(G)q_1(\overline G)\le2n(n-2)$. We prove the former and disprove the latter by constructing a family of graphs $H_n$ where $q_1(H_n)q_1(\overline{H_n})$ is about $2.15n^2+O(n)$.
•We generalized some Nordhaus-Gaddum type bounds of eigenvalues to Aα-eigenvalues.•We study weighted graphs which are generalization of graphs.•We track the gradual change of the Nordhaus-Gaddum type ...results.
Let Gω be a weighted graph, whose adjacency matrix and weighted degree diagnoal matrix are A(Gω) and D(Gω), respectively. For a given α∈0,1, the matrix Aα(Gω)=αD(Gω)+(1−α)A(Gω) is the Aα-matrix of Gω. If all edge weights of Gω are belonging to (0,1), by defining the complement of Gω, we obtain some Nordhaus-Gaddum type bounds concerning Aα-eigenvalues of Gω.
The Wiener polarity index Wp(G) of a graph G is the number of unordered pairs of vertices {u, v} of G such that the distance between u and v is 3. In this paper, we study the Nordhaus–Gaddum-type ...inequality for the Wiener polarity index of a graph G of order n. Due to concerns that both Wp(G) and Wp(G¯) are nontrivial only when diam(G)=3 and diam(G¯)=3, we firstly consider the crucial case and get that 2≤Wp(G)+Wp(G¯)≤⌈n2⌉⌊n2⌋−n+2. Moreover, the bounds are best possible, and the corresponding extremal graphs are also presented. Then we generalize the results to all connected simple graphs. Furthermore, we discuss the Nordhaus–Gaddum-type inequality for trees and unicyclic graphs, respectively.
PDF
