Cycle embedding in star graphs with conditional edge faults

Among the various interconnection networks, the star graph has been an attractive one. In this paper, we consider the cycle embedding problem in star graphs with conditional edge faults. We show that there exist cycles of all even lengths from 6 to n! in an n-dimensional star graph with ?2n-7 edge faults in which each vertex is incident with at least two healthy edges for n?4.     

Estimates on the size of the cycle spectra of Hamiltonian graphs

Given a graph $G$, let $S\left(G\right)$ be the set of all cycle lengths contained in $G$ and let $s\left(G\right)=\left|S\left(G\right)\right|$. Let $?\left(G\right)=\{3,\dots ,n\}?S\left(G\right)$ and let $d$ be the greatest common divisor of $n?2$ and all the positive pairwise differences of elements in $?\left(G\right)$. We prove that if a Hamiltonian graph $G$ of order $n$ has at least $\frac{n(p+2)}{4}+1$ edges, where $p$ is an integer such that $1\le p\le n?2$, then $s\left(G\right)\ge p$ or $G$ is exceptional, by which we mean $d?(??2)$ for some $?\in ?\left(G\right)$. We also discuss cases where $G$ is not exceptional, for example when $n?2$ is prime. Moreover, we show that $s\left(G\right)\ge min\{p,\frac{n?3}{2}\}$, which if $G$ is bipartite implies that $s\left(G\right)\ge min\{?\frac{4(m?1)}{n}?2?,\frac{n?2}{2}\}$, where $m$ is the number of edges in $G$.     

Dirac’s Type Sufficient Conditions for Hamiltonicity and Pancyclicity

Let G = (V, E) be a any simple, undirected graph on n ≥ 3 vertices with the degree sequence . We consider the class of graphs satisfying the condition where , is a positive integer. It is known that is hamiltonian if θ ≤ δ. In this paper,

New sufficient conditions for bipancyclicity of balanced bipartite digraphs

The main results provide sufficient conditions for balanced bipartite digraphs to be bipancyclic. These are analogues to well-known results on pancyclic digraphs.     

Cycles with a chord in dense graphs

A cycle of order $k$ is called a $k$-cycle. A non-induced cycle is called a chorded cycle. Let $n$ be an integer with $n\ge 4$. Then a graph $G$ of order $n$ is chorded pancyclic if $G$ contains a chorded $k$-cycle for every integer $k$ with $4\le k\le n$. Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order $n$ satisfying ${deg}_{G}u+{deg}_{G}v\ge n$ for every pair of nonadjacent vertices $u$,  $v$ in $G$ is chorded pancyclic unless $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, the Cartesian product of $K_3$ and $K_2$. They also conjectured that if $G$ is Hamiltonian, we can replace the degree sum condition with the weaker density condition $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph $G$ of order $n$ with $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ contains a $k$-cycle, then $G$ contains a chorded $k$-cycle, unless $k=4$ and $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, Then observing that $K_{\frac{n}{2},\frac{n}{2}}$ and $K_3\square K_2$ are exceptions only for $k=4$, we further relax the density condition for sufficiently large $k$.     

Pancyclic graphs and linear forests

Given integers k,s,t with 0≤s≤t and k≥0, a (k,t,s)-linear forest F is a graph that is the vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order n≥k+t is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. More generally, given integers m and n with k+t≤m≤n, a graph G of order n is (k,t,s,m)-pancyclic if for any (k,t,s)-linear forest F and for each integer r with m≤r≤n, there is a cycle of length r containing the linear forest F. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)-pancyclic (or just (k,t,m)-pancyclic) are proved.     

Forbidden subgraphs for chorded pancyclicity

We call a graph $G$ pancyclic if it contains at least one cycle of every possible length $m$, for $3\le m\le \left|V\left(G\right)\right|$. In this paper, we define a new property called chorded pancyclicity. We explore forbidden subgraphs in claw-free graphs sufficient to imply that the graph contains at least one chorded cycle of every possible length $4,5,\dots ,\left|V\left(G\right)\right|$. In particular, certain paths and triangles with pendant paths are forbidden.     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

On the Set of Cycle Lengths in a Hamiltonian Graph with a Given Maximum Degree

Let n and be two integers such that 2n–1. We describe the set of cycle lengths occurring in any hamiltonian graph G of order n and maximum degree . We conclude that for the case this set contains all the integers belonging to the union [3,2–n+2][n–+2,+1], and for it contains every integer between 3 and +1. We also study the set of cycle lengths in a hamiltonian graph with two fixed vertices of large degree sum. Our main results imply that the stability s(P) for the property of being pancyclic satisfies