Cycles through three vertices in 2-connected graphs

Let Gbe a 2-connected graph with minimum degree d and let {x, y, z} be a set of three vertices contained on some cycle ofG. ThenG ishamiltonian or {x, y, z} is contained on a cycle of length at least 2d inG.     

On cycles through specified vertices

For a set X of vertices of a graph fulfilling local connectedness conditions, the existence of a cycle containing X is proved.     

Decomposition of cubic graphs with a 2-factor consisting of three cycles

The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We prove that this conjecture is true for connected cubic graphs with a 2-factor consisting of three cycles.     

Counterexamples to a conjecture of mader about cycles through specified vertices inn-edge-connected graphs

For each oddn≥3, we constructn-edge-connected graphsG with the following property: There are two verticesu andv inG such that for every cycleC inG passign throughu andv the graphG-E(C) is not (n-2)-edge-connected. HereE(C) denotes the set of edges ofC, and a cycle is allowed to pass through a vertex more than once.     

The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices

In this paper, we consider the conjugate-Toeplitz (CT) and conjugate-Hankel (CH) matrices. It is proved that the inverse of these special matrices can be expressed as the sum of products of lower and upper triangular matrices. Firstly, we get access to the explicit inverse of conjugate-Toeplitz matrix. Secondly, the decomposition of the inverse is obtained. Similarly, the formulae and the decomposition on inverse of conjugate-Hankel are provided. Thirdly, the stability of the inverse formulae of CT and CH matrices are discussed. Finally, examples are provided to verify the feasibility of the algorithms provided in this paper.     

Embedding cycles of given length in oriented graphs

Kelly, Kühn and Osthus conjectured that for any ?≥4$?\ge 4$ and the smallest number k≥3$k\ge 3$ that does not divide ?$?$, any large enough oriented graph G$G$ with δ⁺(G),δ⁻(G)≥⌊|V(G)|/k⌋+1${\delta }^{+}\left(G\right),{\delta }^{-}\left(G\right)\ge \lfloor \left|V\left(G\right)\right|/k\rfloor +1$ contains a directed cycle of length ?$?$. We prove this conjecture asymptotically for the case when ?$?$ is large enough compared to k$k$ and k≥7$k\ge 7$. The case when k≤6$k\le 6$ was already settled asymptotically by Kelly, Kühn and Osthus.     

Cycles through 4 vertices in 3-connected graphs

S.C. Locke proposed a question: If G is a 3-connected graph with minimum degree d and X is a set of 4 vertices on a cycle in G, must G have a cycle through X with length at least min{2d,|V(G)|}? In this paper, we answer this question.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

On degree sum conditions for long cycles and cycles through specified vertices

Let G be a graph. For S⊂V(G), let Δ_k(S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Δ₂(S)≥d for every independent set S of order κ(G)+1, then G has a cycle of length at least min{d,|V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Δ₂(S)≥|V(G)| for every independent set S of order κ(X)+1 in G[X], then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles.     

Nonseparable graphs with a given number of cycles

G. Ringel conjectured that for every positive integer n other than 2, 4, 5, 8, 9, and 16, there exists a nonseparable graph with n cycles. It is proved here that the conjecture is true even with the restriction to planar and hamiltonian graphs.     

On 2-factor hamiltonian regular bipartite graphs

A k-regular bipartite graph is said to be 2-factor hamiltonian if each of its 2-factor is hamiltonian. It is well known that if a k-regular bipartite graph is 2-factor hamiltonian, then k?Q3. In this paper, we give a new proof of this fact.     

Packing cycles through prescribed vertices under modularity constraints

The well-known theorem of Erd?s–Pósa says that either a graph G has k disjoint cycles or there is a vertex set X   of order at most f(k)$f(k)$ for some function f   such that G?X$G?X$ is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization.     

Cycles through ten vertices in 3-connected cubic graphs

It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore, we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under which it has a cycle through four chosen vertices and two edges. We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices each map to a distinct vertex of the Petersen graph.     

Distance-biregular graphs with 2-valent vertices and distance-regular line graphs

A graph G is called distance-regularized if each vertex of G admits an intersection array. It is known that every distance-regularized graph is either distance-regular (DR) or distance-biregular (DBR). Note that DBR means that the graph is bipartite and the vertices in the same color class have the same intersection array. A (k, g)-graph is a k-regular graph with girth g and with the minimum possible number of vertices consistent with these properties. Biggs proved that, if the line graph L(G) is distance-transitive, then G is either K_1,n or a (k, g)-graph. This result is generalized to DR graphs by showing that the following are equivalent: (1) L(G) is DR and G ≠ K_1,n for n ≥ 2, (2) G and L(G) are both DR, (3) subdivision graph S(G) is DBR, and (4) G is a (k, g)-graph. This result is used to show that a graph S is a DBR graph with 2-valent vertices iff S = K_2,′ or S is the subdivision graph of a (k, g)-graph. Let G⁽²⁾ be the graph with vertex set that of G and two vertices adjacent if at distance two in G. It is shown that for a DBR graph G, G⁽²⁾ is two DR graphs. It is proved that a DR graph H without triangles can be obtained as a component of G⁽²⁾ if and only if it is a (k, g)-graph with g ≥ 4.     

Half-integral packing of odd cycles through prescribed vertices

The well-known theorem of Erd?s-Pósa says that a graph G has either k disjoint cycles or a vertex set X of order at most f(k) for some function f such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we discuss packing disjoint S-cycles, i.e., cycles that are required to go through a set S of vertices. For this problem, Kakimura-Kawarabayashi-Marx (2011) and Pontecorvi-Wollan (2010) recently showed the Erd?s-Pósa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the Erd?s-Pósa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the Erd?s-Pósa-type result for the half-integral packing of odd S-cycles, which is a generalization of Reed (1999) when S=V. That is, we show that given an integer k and a vertex set S, a graph G has either 2k odd S-cycles so that each vertex is in at most two of these cycles, or a vertex set X of order at most f(k) (for some function f) such that G\X has no odd S-cycle.