Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA tight $Q$-index condition for a graph to be $k$-path-coverable involving minimum degree
130
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is $k$-path-coverable if its vertex set $V(G)$ can be covered by $k$ or fewer vertex disjoint paths. In this paper, using the $Q$-index of a connected graph $G$, we present a tight sufficient condition for $G$ with fixed minimum degree and large order to be $k$-path-coverable.
rate research
Read More
We say a graph $G$ has a Hamiltonian path if it has a path containing all vertices of $G$. For a graph $G$, let $sigma_2(G)$ denote the minimum degree sum of two nonadjacent vertices of $G$; restrictions on $sigma_2(G)$ are known as Ore-type conditions. Given an integer $tgeq 5$, we prove that if a connected graph $G$ on $n$ vertices satisfies $sigma_2(G)>{t-3over t-2}n$, then $G$ has either a Hamiltonian path or an induced subgraph isomorphic to $K_{1, t}$. Moreover, we characterize all $n$-vertex graphs $G$ where $sigma_2(G)={t-3over t-2}n$ and $G$ has neither a Hamiltonian path nor an induced subgraph isomorphic to $K_{1, t}$. This is an analogue of a recent result by Mom`ege, who investigated the case when $t=4$.
The quadrilateral graph Q(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 3, whereas the pentagonal graph W(G) is obtained from G by replacing each edge in G with two parallel paths of length 1 and 4. In this paper, closed-form formulas of resistance distance and Kirchhoff index for quadrilateral graph and pentagonal graph are obtained whenever G is an arbitrary graph.
The clique removal lemma says that for every $r geq 3$ and $varepsilon>0$, there exists some $delta>0$ so that every $n$-vertex graph $G$ with fewer than $delta n^r$ copies of $K_r$ can be made $K_r$-free by removing at most $varepsilon n^2$ edges. The dependence of $delta$ on $varepsilon$ in this result is notoriously difficult to determine: it is known that $delta^{-1}$ must be at least super-polynomial in $varepsilon^{-1}$, and that it is at most of tower type in $log varepsilon^{-1}$. We prove that if one imposes an appropriate minimum degree condition on $G$, then one can actually take $delta$ to be a linear function of $varepsilon$ in the clique removal lemma. Moreover, we determine the threshold for such a minimum degree requirement, showing that above this threshold we have linear bounds, whereas below the threshold the bounds are once again super-polynomial, as in the unrestricted removal lemma. We also investigate this question for other graphs besides cliques, and prove some general results about how minimum degree conditions affect the bounds in the graph removal lemma.
ErdH{o}s determined the maximum size of a nonhamiltonian graph of order $n$ and minimum degree at least $k$ in 1962. Recently, Ning and Peng generalized. ErdH{o}s work and gave the maximum size $h(n,c,k)$ of graphs with prescribed order $n$, circumference $c$ and minimum degree at least $k.$ But for some triples $n,c,k,$ the maximum size is not attained by a graph of minimum degree $k.$ For example, $h(15,14,3)=77$ is attained by a unique graph of minimum degree $7,$ not $3.$ In this paper we obtain more precise information by determining the maximum size of a graph with prescribed order, circumference and minimum degree. Consequently we solve the corresponding problem for longest paths. All these results on the size of graphs have cliq
Komlos [Tiling Turan theorems, Combinatorica, 20,2 (2000), 203{218] determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
