Search

Identifying certain conditions that ensure the Hamiltonicity of graphs is highly important and valuable due to the fact that determining whether a graph is Hamiltonian is an NP-complete problem.For a graph G with vertex set V(G) and edge set E(G), the first Zagreb index ( M 1 ) and second Zagreb index ( M 2 ) are defined as M 1 (G) = ∑ v i v j ∈ E (G) (d G (v i) + d G (v j)) and M 2 (G) = ∑ v i v j ∈ E (G) d G (v i) d G (v j) , where d G (v i) denotes the degree of vertex v i ∈ V (G) . The difference of Zagreb indices ( Δ M ) of G is defined as Δ M (G) = M 2 (G) - M 1 (G) .In this paper, we try to look for the relationship between structural graph theory and chemical graph theory. We obtain some sufficient conditions, with regards to Δ M (G) , for graphs to be k-hamiltonian, traceable, k-edge-hamiltonian, k-connected, Hamilton-connected or k-path-coverable. [ABSTRACT FROM AUTHOR]

A compatible Euler trail (tour) in an edge-colored graph is an Euler trail (tour) in which each two edges traversed consecutively along the Euler trail (tour) have distinct colors. In this paper, we show that the problem of counting compatible Euler trails in edge-colored graphs is # P-complete, and develop O(mN) time algorithms for enumerating compatible Euler trails (tours) in edge-colored graphs with m edges and N compatible Euler trails (tours). It is worth mentioning that our algorithms can run in O(N) time when there is no vertex v with degree 4 and maximum monochromatic degree 2. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n with adjacency matrix A(G) and diagonal matrix D(G). For any real α ∈ [ 0 , 1 ] , denote A α (G) : = α D (G) + (1 - α) A (G) be A α -matrix of graph G. The eigenvalues of A α (G) are λ 1 (A α (G)) ≥ λ 2 (A α (G)) ≥ ⋯ ≥ λ n (A α (G)) , the largest eigenvalue λ 1 (A α (G)) is called the A α -spectral radius of G. The A α -separator S A α (G) of graph G is defined as S A α (G) = λ 1 (A α (G)) - λ 2 (A α (G)) . For two disjoint graphs G 1 and G 2 (where V (G 1) and V (G 2) are disjoint with v 1 ∈ V (G 1) , v 2 ∈ V (G 2) ); the coalescence of G 1 and G 2 with respect to v 1 and v 2 is formed by identifying v 1 and v 2 and is denoted by G 1 · G 2 . The A α -characteristic polynomial of G is defined to be Φ (A α ; x) = d e t (x I n - A α (G)) , where I n is the identity matrix of size n. A unicyclic graph is a simple connected graph in which the number of edges is equal to the number of vertices. In this paper, firstly, we give the A α -characteristic polynomial of the coalescent graph, and A α -eigenvalues of the star graph for the application. Secondly, we study the extremal graphs with the maximum and minimum A α -spectral radius of the unicyclic graph. Finally, we present the extremal graph with the maximum A α -separator of the unicyclic graph and calculate the range of A α -separator of the corresponding extremal graph. [ABSTRACT FROM AUTHOR]

A compatible spanning circuit in a (not necessarily properly) edge-colored graph G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours), and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature. More recently, sufficient conditions for the existence of more general compatible spanning circuits in specific edge-colored graphs have been established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erdős from the 1970s. [ABSTRACT FROM AUTHOR]

Let P be a cubic 3-connected bipartite plane graph having a 2-factor which consists only of facial 4-cycles, and suppose that P ∗ is the dual graph. We show that P has at least 3 2 | P ∗ | Δ 2 (P ∗) different Hamilton cycles. [ABSTRACT FROM AUTHOR]

A hamiltonian walk of a digraph is a closed spanning directed walk with minimum length in the digraph. The length of a hamiltonian walk in a digraph D is called the hamiltonian number of D, denoted by h( D). In Chang and Tong (J Comb Optim 25:694-701, 2013), Chang and Tong proved that for a strongly connected digraph D of order n, $$n\le h(D)\le \lfloor \frac{(n+1)^2}{4} \rfloor $$ , and characterized the strongly connected digraphs of order n with hamiltonian number $$\lfloor \frac{(n+1)^2}{4} \rfloor $$ . In the paper, we characterized the strongly connected digraphs of order n with hamiltonian number $$\lfloor \frac{(n+1)^2}{4} \rfloor -1$$ and show that for any triple of integers n, k and t with $$n\ge 5$$ , $$n\ge k\ge 3$$ and $$t\ge 0$$ , there is a class of nonisomorphic digraphs with order n and hamiltonian number $$n(n-k+1)-t$$ . [ABSTRACT FROM AUTHOR]

Let $$\mathcal{B}$$ denote the class of all 3-connected cubic bipartite plane graphs. A conjecture of Barnette states that every graph in $$\mathcal{B}$$ has a Hamilton cycle. A cyclic sequence of big faces is a cyclic sequence of different faces, each bounded by at least six edges, such that two faces from the sequence are adjacent if and only if they are consecutive in the sequence. Suppose that $${F_1, F_2, F_3}$$ is a proper 3-coloring of the faces of $$G^*\in \mathcal{B}$$ . We prove that if every cyclic sequence of big faces of $$G^*$$ has a face belonging to $$F_1$$ and a face belonging to $$F_2$$ , then $$G^*$$ has the following properties: $$H^{+-}$$ : If any two edges are chosen on the same face, then there is a Hamilton cycle through one and avoiding the other, $$H^{--}$$ : If any two edges are chosen which are an even distance apart on the same face, then there is a Hamilton cycle that avoids both. Moreover, let $$X$$ and $$Y$$ partition the set of big faces of $$G^*$$ such that all such faces of $$F_1$$ are in $$X$$ and all such faces of $$F_2$$ are in $$Y$$ . We prove that if every cyclic sequence of big faces has a face belonging to $$X$$ and a face belonging to $$Y$$ , then $$G^*$$ has a Hamilton cycle. [ABSTRACT FROM AUTHOR]