Zobrazeno 1 - 10
of 71
pro vyhledávání: '"05C50, 05C70"'
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{
Externí odkaz:
http://arxiv.org/abs/2403.02896
Publikováno v:
Discrete Applied Mathematics 360(2025)188-195
A graph $G$ contains a strong parity factor $F$ if for every subset $X\subseteq V(G)$ with $|X|$ even, $G$ has a spanning subgraph $F$ satisfying $\delta(F)\geq1$, $d_F(u)\equiv1$ (mod 2) for any $u\in X$, and $d_F(v)\equiv0$ (mod 2) for any $v\in V(
Externí odkaz:
http://arxiv.org/abs/2402.13601
Autor:
Liu, Chang, Li, Jianping
In this paper, we study some spanning trees with bounded degree and leaf degree from eigenvalues. For any integer $k\geq2$, a $k$-tree is a spanning tree in which every vertex has degree no more than $k$. Let $T$ be a spanning tree of a connected gra
Externí odkaz:
http://arxiv.org/abs/2311.12417
Autor:
Zhou, Sizhong, Zhang, Yuli
Let $a$ and $b$ be two positive integers with $a\leq b$, and let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. Let $h:E(G)\rightarrow[0,1]$ be a function. If $a\leq\sum\limits_{e\in E_G(v)}{h(e)}\leq b$ holds for every $v\in V(G)$, then
Externí odkaz:
http://arxiv.org/abs/2309.09279
For a nonnegative integer $k$, a graph $G$ is said to be $k$-factor-critical if $G-Q$ admits a perfect matching for any $Q\subseteq V(G)$ with $|Q|=k$. In this article, we prove spectral radius conditions for the existence of $k$-factor-critical grap
Externí odkaz:
http://arxiv.org/abs/2306.16849
Autor:
Zhou, Sizhong, Zhang, Yuli
Let $k$ and $n$ be two nonnegative integers with $n\equiv0$ (mod 2), and let $G$ be a graph of order $n$ with a 1-factor. Then $G$ is said to be $k$-extendable for $0\leq k\leq\frac{n-2}{2}$ if every matching in $G$ of size $k$ can be extended to a 1
Externí odkaz:
http://arxiv.org/abs/2303.16687
Autor:
Cardinal, Jean, Steiner, Raphael
We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless $P=NP$, there is no polynomial-time algorithm that computes a path of constant length between two
Externí odkaz:
http://arxiv.org/abs/2210.14608
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be a diagonal matrix of the degrees of $G$. In 2017, Nikiforov defined the $A_{\alpha}$-matrix of $G$ as \begin{equation*} A_{\alpha}(G)=\alpha G)+(1-\alpha)A(G), \end{equation*}d where $
Externí odkaz:
http://arxiv.org/abs/2203.13415
Sharp bounds on the least eigenvalue of an arbitrary graph are presented. Necessary and sufficient (just sufficient) conditions for the lower (upper) bound to be attained are deduced using edge clique partitions. As an application, we prove that the
Externí odkaz:
http://arxiv.org/abs/2201.01224
Autor:
Kim, Donggyu, O, Suil
Let $G$ be a graph and let $g, f$ be nonnegative integer-valued functions defined on $V(G)$ such that $g(v) \le f(v)$ and $g(v) \equiv f(v) \pmod{2}$ for all $v \in V(G)$. A $(g,f)$-parity factor of $G$ is a spanning subgraph $H$ such that for each v
Externí odkaz:
http://arxiv.org/abs/2111.12966