Let $A(G)$ and $D(G)$ be the adjacency matrix and the degree matrix of $G$, respectively. For any real $\alpha \in [0,1]$, Nikiforov [12] defined the matrix $A_{\alpha}(G)$ as \[ A_{\alpha}(G) …
Let $A(G)$ and $D(G)$ be the adjacency matrix and the degree matrix of $G$, respectively. For any real $\alpha \in [0,1]$, Nikiforov [12] defined the matrix $A_{\alpha}(G)$ as \[ A_{\alpha}(G) = \alpha D(G) + (1-\alpha) A(G). \] An $[a,b]$-factor of a graph $G$ is a spanning subgraph $H$ such that $a \leq d_{H}(v) \leq b$ for any $v \in V(G)$, where $a$ and $b$ are positive integers. In this paper, we give an upper bound of $A_{\alpha}$-spectral radius of graphs with unique perfect matching, and then present $A_{\alpha}$-spectral conditions for the existence of an $[a,b]$-factor in a graph. Our results extend the result of Fan et al. in [4] for the unique perfect matching and $[a,b]$-factor of graphs, and that of Zhao et al. in [16] for a $[1,b]$-odd factor of graphs.
Let $G$ be a connected graph of order $n$ with $n\geq25$. A $\{P_3,P_4,P_5\}$-factor is a spanning subgraph $H$ of $G$ such that every component of $H$ is isomorphic to an …
Let $G$ be a connected graph of order $n$ with $n\geq25$. A $\{P_3,P_4,P_5\}$-factor is a spanning subgraph $H$ of $G$ such that every component of $H$ is isomorphic to an element of $\{P_3,P_4,P_5\}$. Nikiforov introduced the $A_{\alpha}$-matrix of $G$ as $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G)$ [V. Nikiforov, Merging the $A$- and $Q$-spectral theories, Appl. Anal. Discrete Math. 11 (2017) 81--107], where $\alpha\in[0,1]$, $D(G)$ denotes the diagonal matrix of vertex degrees of $G$ and $A(G)$ denotes the adjacency matrix of $G$. The largest eigenvalue of $A_{\alpha}(G)$, denoted by $\lambda_{\alpha}(G)$, is called the $A_{\alpha}$-spectral radius of $G$. In this paper, it is proved that $G$ has a $\{P_3,P_4,P_5\}$-factor unless $G=K_1\vee(K_{n-2}\cup K_1)$ if $\lambda_{\alpha}(G)\geq\lambda_{\alpha}(K_1\vee(K_{n-2}\cup K_1))$, where $\alpha$ be a real number with $0\leq\alpha<\frac{2}{3}$.
An $[a,b]$-factor of a graph $G$ is a spanning subgraph $H$ such that $a\leq d_{H}(v)\leq b$ for each $v\in V(G)$. In this paper, we provide spectral conditions for the existence …
An $[a,b]$-factor of a graph $G$ is a spanning subgraph $H$ such that $a\leq d_{H}(v)\leq b$ for each $v\in V(G)$. In this paper, we provide spectral conditions for the existence of an odd $[1,b]$-factor in a connected graph with minimum degree $\delta$ and the existence of an $[a,b]$-factor in a graph, respectively. Our results generalize and improve some previous results on perfect matchings of graphs. For $a=1$, we extend the result of O\cite{S.O} to obtain an odd $[1,b]$-factor and further improve the result of Liu, Liu and Feng\cite{W.L} for $a=b=1$. For $n\geq 3a+b-1$, we confirm the conjecture of Cho, Hyun, O and Park\cite{E.C}. We conclude some open problems in the end.
An $[a,b]$-factor of a graph $G$ is a spanning subgraph $H$ such that $a\leq d_{H}(v)\leq b$ for each $v\in V(G)$. In this paper, we provide spectral conditions for the existence …
An $[a,b]$-factor of a graph $G$ is a spanning subgraph $H$ such that $a\leq d_{H}(v)\leq b$ for each $v\in V(G)$. In this paper, we provide spectral conditions for the existence of an odd $[1,b]$-factor in a connected graph with minimum degree $\delta$ and the existence of an $[a,b]$-factor in a graph, respectively. Our results generalize and improve some previous results on perfect matchings of graphs. For $a=1$, we extend the result of O\cite{S.O} to obtain an odd $[1,b]$-factor and further improve the result of Liu, Liu and Feng\cite{W.L} for $a=b=1$. For $n\geq 3a+b-1$, we confirm the conjecture of Cho, Hyun, O and Park\cite{E.C}. We conclude some open problems in the end.
An[a,b]-factor of a graph G is a spanning subgraph H in which the degree of each vertex v satisfies a ? dH (v) ? b. In particular, when a = …
An[a,b]-factor of a graph G is a spanning subgraph H in which the degree of each vertex v satisfies a ? dH (v) ? b. In particular, when a = b = k, it is also called a k-factor. Let Q(G) and q(G) be the Q-matrix and the Q-spectral radius of G, respectively. Motivated by the conjecture of Cho, Hyun, O and Park [Bull. Korean Math. Soc. 58 (2021) 31-46] and the result of the spectral radius obtained by Fan, Lin and Lu [Discrete Math. 345 (2022) 112892], we in this paper consider the Q-spectral version of the above conjecture and present a tight sufficient condition in terms of the Q-spectral radius to guarantee the existence of [a, b]-factors in a graph.
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For any real $\alpha\in [0,1]$, Nikiforov [Merging the $A$- …
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For any real $\alpha\in [0,1]$, Nikiforov [Merging the $A$- and $Q$-spectral theories, Appl. Anal. Discrete Math. 11 (2017) 81--107] defined the matrix $A_{\alpha}(G)$ as $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G).$ Let $u$ and $v$ be two vertices of a connected graph $G$. Suppose that $u$ and $v$ are connected by a path $w_0(=v)w_1\cdots w_{s-1}w_s(=u)$ where $d(w_i)=2$ for $1\leq i\leq s-1$. Let $G_{p,s,q}(u,v)$ be the graph obtained by attaching the paths $P_p$ to $u$ and $P_q$ to $v$. Let $s=0,1$. Nikiforov and Rojo [On the $\alpha$-index of graphs with pendent paths, Linear Algebra Appl. 550 (2018) 87--104] conjectured that $\rho_{\alpha}(G_{p,s,q}(u,v))<\rho_{\alpha}(G_{p-1,s,q+1}(u,v))$ if $p\geq q+2.$ In this paper, we confirm the conjecture. As applications, firstly, the extremal graph with maximal $A_{\alpha}$-spectral radius with fixed order and cut vertices is characterized. Secondly, we characterize the extremal tree which attains the maximal $A_{\alpha}$-spectral radius with fixed order and matching number. These results generalize some known results.
Let $G$ be a connected graph of order $n$ with $n\geq16$. A $\{K_{1,2},K_{1,3},K_{5}\}$-factor of $G$ is a spanning subgraph of $G$, in which each component is isomorphic to a member …
Let $G$ be a connected graph of order $n$ with $n\geq16$. A $\{K_{1,2},K_{1,3},K_{5}\}$-factor of $G$ is a spanning subgraph of $G$, in which each component is isomorphic to a member in $\{K_{1,2},K_{1,3},K_{5}\}$. The $A_{\alpha}$-spectral radius of $G$ is denoted by $\rho_{\alpha}(G)$. In this paper, we obtain a lower bound on the size (resp. the $A_{\alpha}$-spectral radius for $\alpha\in[0,\frac{1}{2}]$) of $G$ to guarantee that $G$ has a $\{K_{1,2},K_{1,3},K_{5}\}$-factor, and show that $G$ has a $\{K_{1,2},K_{1,3},K_{5}\}$-factor if $\rho_{\alpha}(G)>\tau(n)$, where $\tau(n)$ is the largest root of $x^3-((\alpha+1)n+\alpha-3)x^2+(\alpha n^2+(\alpha^2-\alpha-1)n-2\alpha+1)x-\alpha^2n^2+(3\alpha^2-\alpha+1)n-4\alpha^2+5\alpha-3=0$.
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For any real $α\in [0,1]$, Nikiforov [Merging the $A$- …
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For any real $α\in [0,1]$, Nikiforov [Merging the $A$- and $Q$-spectral theories, Appl. Anal. Discrete Math. 11 (2017) 81--107] defined the matrix $A_α(G)$ as $A_α(G)=αD(G)+(1-α)A(G).$ Let $u$ and $v$ be two vertices of a connected graph $G$. Suppose that $u$ and $v$ are connected by a path $w_0(=v)w_1\cdots w_{s-1}w_s(=u)$ where $d(w_i)=2$ for $1\leq i\leq s-1$. Let $G_{p,s,q}(u,v)$ be the graph obtained by attaching the paths $P_p$ to $u$ and $P_q$ to $v$. Let $s=0,1$. Nikiforov and Rojo [On the $α$-index of graphs with pendent paths, Linear Algebra Appl. 550 (2018) 87--104] conjectured that $ρ_α(G_{p,s,q}(u,v))
Let $G$ be a graph and $h: E(G)\rightarrow [0,1]$ be a function. For any two positive integers $a$ and $b$ with $a\leq b$, a fractional $[a,b]$-factor of $G$ with the …
Let $G$ be a graph and $h: E(G)\rightarrow [0,1]$ be a function. For any two positive integers $a$ and $b$ with $a\leq b$, a fractional $[a,b]$-factor of $G$ with the indicator function $h$ is a spanning subgraph with vertex set $V(G)$ and edge set $E_h$ such that $a\leq\sum_{e\in E_{G}(v)}h(e)\leq b$ for any vertex $v\in V(G)$, where $E_h = \{e\in E(G)|h(e)>0\}$ and $E_{G}(v)=\{e\in E(G)| e~\mbox{is incident with}~v~\mbox{in}~G\}$. A graph $G$ is ID-factor-critical if for every independent set $I$ of $G$ whose size has the same parity as $|V(G)|$, $G-I$ has a perfect matching. In this paper, we present a tight sufficient condition based on the spectral radius for a graph to contain a fractional $[a,b]$-factor, which extends the result of Wei and Zhang [Discrete Math. 346 (2023) 113269]. Furthermore, we also prove a tight sufficient condition in terms of the spectral radius for a graph with minimum degree $\delta$ to be ID-factor-critical.
Let $K_ℓ^-$ denote the graph obtained from $K_ℓ$ by deleting one edge. We show that for every $γ >0$ and every integer $ℓ≥4$ there exists an integer $n_0=n_0(γ ,ℓ)$ such …
Let $K_ℓ^-$ denote the graph obtained from $K_ℓ$ by deleting one edge. We show that for every $γ >0$ and every integer $ℓ≥4$ there exists an integer $n_0=n_0(γ ,ℓ)$ such that every graph $G$ whose order $n≥n_0$ is divisible by $ℓ$ and whose minimum degree is at least $(\frac{ℓ^2-3ℓ+1}{/ ℓ(ℓ-2)}+γ )n$ contains a $K_ℓ^-$-factor, i.e. a collection of disjoint copies of $K_ℓ^-$ which covers all vertices of $G$. This is best possible up to the error term $γn$ and yields an approximate solution to a conjecture of Kawarabayashi.
Let $\alpha\in[0,1)$, and let $G$ be a connected graph of order $n$ with $n\geq f(\alpha)$, where $f(\alpha)=14$ for $\alpha\in[0,\frac{1}{2}]$, $f(\alpha)=17$ for $\alpha\in(\frac{1}{2},\frac{2}{3}]$, $f(\alpha)=20$ for $\alpha\in(\frac{2}{3},\frac{3}{4}]$ and $f(\alpha)=\frac{5}{1-\alpha}+1$ for $\alpha\in(\frac{3}{4},1)$. A …
Let $\alpha\in[0,1)$, and let $G$ be a connected graph of order $n$ with $n\geq f(\alpha)$, where $f(\alpha)=14$ for $\alpha\in[0,\frac{1}{2}]$, $f(\alpha)=17$ for $\alpha\in(\frac{1}{2},\frac{2}{3}]$, $f(\alpha)=20$ for $\alpha\in(\frac{2}{3},\frac{3}{4}]$ and $f(\alpha)=\frac{5}{1-\alpha}+1$ for $\alpha\in(\frac{3}{4},1)$. A path factor is a spanning subgraph $F$ of $G$ such that every component of $F$ is a path with at least two vertices. Let $k\geq2$ be an integer. A $P_{\geq k}$-factor means a path-factor with each component being a path of order at least $k$. A graph $G$ is called a $P_{\geq k}$-factor covered graph if $G$ has a $P_{\geq k}$-factor containing $e$ for any $e\in E(G)$. Let $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G)$, where $D(G)$ denotes the diagonal matrix of vertex degrees of $G$ and $A(G)$ denotes the adjacency matrix of $G$. The largest eigenvalue of $A_{\alpha}(G)$ is called the $A_{\alpha}$-spectral radius of $G$, which is denoted by $\rho_{\alpha}(G)$. In this paper, it is proved that $G$ is a $P_{\geq2}$-factor covered graph if $\rho_{\alpha}(G)>\eta(n)$, where $\eta(n)$ is the largest root of $x^{3}-((\alpha+1)n+\alpha-4)x^{2}+(\alpha n^{2}+(\alpha^{2}-2\alpha-1)n-2\alpha+1)x-\alpha^{2}n^{2}+(5\alpha^{2}-3\alpha+2)n-10\alpha^{2}+15\alpha-8=0$. Furthermore, we provide a graph to show that the bound on $A_{\alpha}$-spectral radius is optimal.
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.
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.
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.
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.