اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe relation between Hamiltonian and $1$-tough properties of the Cartesian product graphs
109
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph $G_1square G_2$ of graphs $G_1$ and $G_2$ satisfying that $G_1$ is traceable and $G_2$ is connected with a path factor. Let Pn be the path of order $n$ and $H$ be a connected bipartite graph. With certain requirements of $n$, we show that the following three statements are equivalent: (i) $P_nsquare H$ is Hamiltonian; (ii) $P_nsquare H$ is $1$-tough; and (iii) $H$ has a path factor.
قيم البحث
اقرأ أيضاً
The toughness of a noncomplete graph $G$ is the maximum real number $t$ such that the ratio of $|S|$ to the number of components of $G-S$ is at least $t$ for every cutset $S$ of $G$, and the toughness of a complete graph is defined to be $infty$. Det
ermining the toughness for a given graph is NP-hard. Chv{a}tals toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chv{a}tals toughness conjecture for $(P_3cup 2P_1)$-free graphs by showing that every 7-tough $(P_3cup 2P_1)$-free graph on at least three vertices is hamiltonian.
Let $G$ be a $t$-tough graph on $nge 3$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $G$ is greater than $frac{n}{t+1}-1$, then $G$ is hamiltonian. In terms of Ores conditions in this direction, the prob
lem was only studied when $t$ is between 1 and 2. In this paper, we show that if the degree sum of any two nonadjacent vertices of $G$ is greater than $frac{2n}{t+1}+t-2$, then $G$ is hamiltonian.
Let $G=(V,E)$ be a graph and $Gamma $ an Abelian group both of order $n$. A $Gamma$-distance magic labeling of $G$ is a bijection $ell colon Vrightarrow Gamma $ for which there exists $mu in Gamma $ such that $% sum_{xin N(v)}ell (x)=mu $ for all $vi
n V$, where $N(v)$ is the neighborhood of $v$. Froncek %(cite{ref_CicAus}) showed that the Cartesian product $C_m square C_n$, $m, ngeq3$ is a $mathbb{Z}_{mn}$-distance magic graph if and only if $mn$ is even. It is also known that if $mn$ is even then $C_m square C_n$ has $mathbb{Z}_{alpha}times mathcal{A}$-magic labeling for any $alpha equiv 0 pmod {{rm lcm}(m,n)}$ and any Abelian group $mathcal{A}$ of order $mn/alpha$. %cite{ref_CicAus} However, the full characterization of group distance magic Cartesian product of two cycles is still unknown. In the paper we make progress towards the complete solution this problem by proving some necessary conditions. We further prove that for $n$ even the graph $C_{n}square C_{n}$ has a $Gamma$-distance magic labeling for any Abelian group $Gamma$ of order $n^{2}$. Moreover we show that if $m eq n$, then there does not exist a $(mathbb{Z}_2)^{m+n}$-distance magic labeling of the Cartesian product $C_{2^m} square C_{2^{n}}$. We also give necessary and sufficient condition for $C_{m} square C_{n}$ with $gcd(m,n)=1$ to be $Gamma$-distance magic.
Let $G$ be a finite connected graph on two or more vertices and $G^{[N,k]}$ the distance $k$-graph of the $N$-fold Cartesian power of $G$. For a fixed $kge1$, we obtain explicitly the large $N$ limit of the spectral distribution (the eigenvalue distr
ibution of the adjacency matrix) of $G^{[N,k]}$. The limit distribution is described in terms of the Hermite polynomials. The proof is based on asymptotic combinatorics along with quantum probability theory.
Chv{a}tal conjectured in 1973 the existence of some constant $t$ such that all $t$-tough graphs with at least three vertices are hamiltonian. While the conjecture has been proven for some special classes of graphs, it remains open in general. We say
that a graph is $(K_2 cup 3K_1)$-free if it contains no induced subgraph isomorphic to $K_2 cup 3K_1$, where $K_2 cup 3K_1$ is the disjoint union of an edge and three isolated vertices. In this paper, we show that every 3-tough $(K_2 cup 3K_1)$-free graph with at least three vertices is hamiltonian.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
