اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn traceable iterated line graph and hamiltonian path index
378
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Xiong and Liu [L. Xiong and Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422] gave a characterization of the graphs $G$ for which the $n$-th iterated line graph $L^n(G)$ is hamiltonian, for $nge2$. In this paper, we study the existence of a hamiltonian path in $L^n(G)$, and give a characterization of $G$ for which $L^n(G)$ has a hamiltonian path. As applications, we use this characterization to give several upper bounds on the hamiltonian path index of a graph.
قيم البحث
اقرأ أيضاً
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.
For a non-negative integer $sle |V(G)|-3$, a graph $G$ is $s$-Hamiltonian if the removal of any $kle s$ vertices results in a Hamiltonian graph. Given a connected simple graph $G$ that is not isomorphic to a path, a cycle, or a $K_{1,3}$, let $delta(
G)$ denote the minimum degree of $G$, let $h_s(G)$ denote the smallest integer $i$ such that the iterated line graph $L^{i}(G)$ is $s$-Hamiltonian, and let $ell(G)$ denote the length of the longest non-closed path $P$ in which all internal vertices have degree 2 such that $P$ is not both of length 2 and in a $K_3$. For a simple graph $G$, we establish better upper bounds for $h_s(G)$ as follows. begin{equation*} h_s(G)le left{ begin{aligned} & ell(G)+1, &&mbox{ if }delta(G)le 2 mbox{ and }s=0; & widetilde d(G)+2+lceil lg (s+1)rceil, &&mbox{ if }delta(G)le 2 mbox{ and }sge 1; & 2+leftlceillgfrac{s+1}{delta(G)-2}rightrceil, && mbox{ if } 3ledelta(G)le s+2; & 2, &&{rm otherwise}, end{aligned} right. end{equation*} where $widetilde d(G)$ is the smallest integer $i$ such that $delta(L^i(G))ge 3$. Consequently, when $s ge 5$, this new upper bound for the $s$-hamiltonian index implies that $h_s(G) = o(ell(G)+s+1)$ as $s to infty$. This sharpens the result, $h_s(G)leell(G)+s+1$, obtained by Zhang et al. in [Discrete Math., 308 (2008) 4779-4785].
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.
Let $ Pi_q $ be the projective plane of order $ q $, let $psi(m):=psi(L(K_m))$ the pseudoachromatic number of the complete line graph of order $ m $, let $ ain { 3,4,dots,tfrac{q}{2}+1 } $ and $ m_a=(q+1)^2-a $. In this paper, we improve the upper
bound of $ psi(m) $ given by Araujo-Pardo et al. [J Graph Theory 66 (2011), 89--97] and Jamison [Discrete Math. 74 (1989), 99--115] in the following values: if $ xgeq 2 $ is an integer and $min {4x^2-x,dots,4x^2+3x-3}$ then $psi(m) leq 2x(m-x-1)$. On the other hand, if $ q $ is even and there exists $ Pi_q $ we give a complete edge-colouring of $ K_{m_a} $ with $(m_a-a)q$ colours. Moreover, using this colouring we extend the previous results for $a={-1,0,1,2}$ given by Araujo-Pardo et al. in [J Graph Theory 66 (2011), 89--97] and [Bol. Soc. Mat. Mex. (2014) 20:17--28] proving that $psi(m_a)=(m_a-a)q$ for $ ain {3,4,dots,leftlceil frac{1+sqrt{4q+9}}{2}rightrceil -1 } $.
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 conditio
ns. 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$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
