Search

A graph invariant, in the sense of graph automorphism, is a mapping from the set of graphs to the reals. Numerous topological indices have been proposed to characterize the topological properties of graphs, and they are widely recognized as graph invariants. Some sufficient conditions in terms of certain topological indices have been suggested to describe hamiltonian properties of graphs, such as Hamiltonicity, traceability, Hamiltonian-connectedness, k-leaf-connectedness, as well as β -deficiency. For a graph G, the first and second Zagreb indices are defined as M 1 (G) = ∑ u ∈ V (G) d u 2 and M 2 (G) = ∑ u v ∈ E (G) d u d v , where d u denotes the degree of vertex u in G. The difference of Zagreb indices of G is defined as Δ M (G) = M 2 (G) - M 1 (G) . In this paper, we suggest some sufficient conditions in terms of Δ M (G) for graphs to be Hamiltonian, Hamiltonian-connected and β -deficient, respectively. [ABSTRACT FROM AUTHOR]

Let G be a finite group, let Irr(G) be the set of all complex irreducible characters of G and let cd(G) be the set of all degrees of characters in [Formula: see text] Let [Formula: see text] be the set of all primes that divide some degrees in [Formula: see text] The character degree graph [Formula: see text] of G is the simple undirected graph with vertex set [Formula: see text] and in which two distinct vertices p and q are adjacent if there exists a character degree [Formula: see text] such that r is divisible by the product pq. In this paper we obtain a necessary condition for the character degree graph [Formula: see text] of a solvable group G to be eulerian. We also prove that every n – 2 regular graph on n vertices where n is even and [Formula: see text] is the character degree graph of some solvable group. In the last part of the paper we give a bound for the number of Eulerian character degree graphs in terms of number of vertices.

Xiong and Liu [21] gave a characterization of the graphs G for which the n-iterated line graph Ln(G) is hamiltonian, for n ≥ 2. In this paper, we study the existence of a hamiltonian path in Ln(G), and give a characterization of G for which Ln(G) has a hamiltonian path. As applications, we use this characterization to give several upper bounds on the hamiltonian path index of a graph. [ABSTRACT FROM AUTHOR]

Let G be a finite group with identity e and H ≠ { e } be a subgroup of G. The generalized non-coprime graph Γ G , H of G with respect to H is the simple undirected graph with G \ { e } as the vertex set and two distinct vertices x and y are adjacent if and only if gcd (| x | , | y |) ≠ 1 and either x ∈ H or y ∈ H , where |x| is the order of x ∈ G . In this paper, we study certain graph theoretical properties of generalized non-coprime graphs of finite groups, concentrating on cyclic groups. More specifically, we obtain necessary and sufficient conditions for the generalized non-coprime graph of a cyclic group to be in the class of stars, paths, triangle-free, complete bipartite, complete, split, claw-free, chordal or perfect graphs. Then we show that widening the class of groups to all finite nilpotent groups gives us no new graphs, but we give as an example of contrasting behaviour the class of EPPO groups (those in which all elements have prime power order). We conclude with a connection to the Gruenberg–Kegel graph. [ABSTRACT FROM AUTHOR]

Let G be a finite group generated by S and C(G, S) the Cayley digraphs of G with connection set S. In this paper, we give some sufficient conditions for the existence of hamiltonian circuit in C(G, S), where G = Zm ⋊ H is a semiproduct of Zm by a subgroup H of G. In particular, if m is a prime, then the Cayley digraph of G has a hamiltonian circuit unless G = Zm × H. In addition, we introduce a new digraph operation, called φ-semiproduct of Γ1 by Γ2 and denoted by Γ1 ⋊φ Γ2, in terms of mapping φ: V(Γ2) → {1, −1}. Furthermore we prove that C(Zm, {a}) ⋊φC(H, S) is also a Cayley digraph if φ is a homomorphism from H to { 1 , − 1 } ≤ Z m ∗ , which produces some classes of Cayley digraphs that have hamiltonian circuits. [ABSTRACT FROM AUTHOR]

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 spanning circuit in an edge-colored graph G (not necessarily properly) is defined as a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. The existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and compatible Euler tours) has been studied extensively. Recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times in specific edge-colored graphs satisfying certain degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of such compatible s-panning circuits. We consider edge-colored graphs containing no certain forbidden induced subgraphs. As applications, we also consider the existence of such compatible spanning circuits in edge-colored graphs G with κ(G) ≥ α(G), κ(G) ≥ α(G) − 1 and κ (G) ≥ α(G), respectively. In this context, κ(G), α(G) and κ (G) denote the connectivity, the independence number and the edge connectivity of a graph G, respectively. [ABSTRACT FROM AUTHOR]

An n-vertex graph G is called Hamiltonian if it contains a cycle of length n. Denote by δ (G) the minimum degree of G. The celebrated Dirac theorem states that every n-vertex graph with δ (G) ≥ n / 2 is Hamiltonian for n ≥ 3 . In the present paper, we identify all 2-connected n-vertex non-Hamiltonian graphs with δ (G) ≥ ⌊ n / 2 ⌋ - 1 for n ≥ 21 . [ABSTRACT FROM AUTHOR]

In this paper, we study some problems related to subspace inclusion graph $ \mathop {\mathcal {I}n}(\mathbb {V}) $ I n ⁡ (V) and subspace sum graph $ \mathcal {G}(\mathbb {V}) $ G (V) of a finite-dimensional vector space $ \mathbb {V} $ V . Namely, we prove that $ \mathop {\mathcal {I}n}(\mathbb {V}) $ I n ⁡ (V) is a Cayley graph as well as Hamiltonian when the dimension of $ \mathbb {V} $ V is 3. We also find the exact value of independence number of $ \mathcal {G}(\mathbb {V}) $ G (V) when the dimension of $ \mathbb {V} $ V is odd. The above two problems were left open in previous works in the literature. Moreover, we prove that the determining numbers of $ \mathop {\mathcal {I}n}(\mathbb {V}) $ I n ⁡ (V) and $ \mathcal {G}(\mathbb {V}) $ G (V) are bounded above by 6. Finally, we study some forbidden subgraphs of these two graphs. [ABSTRACT FROM AUTHOR]

Denote by r g (G , H) the global resilience of a graph G with respect to Hamiltonicity. That is, r g (G , H) is the minimal r for which there exists a subgraph H ⊆ G with r edges, such that G \ H is not Hamiltonian. We show that if p is above the Hamiltonicity threshold and G ∼ G (n , p) then, with high probability, (We say that a sequence of events (A n) n = 1 ∞ occurs with high probability if lim n → ∞ P (A n) = 1 .) r g (G , H) = δ (G) - 1 . This is easily extended to the full interval: for every p (n) ∈ [ 0 , 1 ] , if G ∼ G (n , p) then, with high probability, r g (G , H) = max { 0 , δ (G) - 1 } . [ABSTRACT FROM AUTHOR]

We compute Hirano's formula for the mod 2 arithmetic Dijkgraaf–Witten invariant Z k for the ring of integers of the quadratic field k = Q ( p 1 ⋯ p r ) , where p i 's are distinct prime numbers with p i ≡ 1 (mod 4) , and give a simple formula for Z k in terms of the graph obtained from quadratic residues among p 1 , ... , p r . Our result answers the question posed by Ken Ono. We also give a density formula for mod 2 arithmetic Dijkgraaf–Witten invariants. [ABSTRACT FROM AUTHOR]

Let D be a digraph with vertex set V(D) and arc set A(D). An antidirected Hamiltonian path (resp. cycle) of D is a Hamiltonian path (resp. cycle) in which consecutive arcs have opposite directions and each arc of D occurs exactly once. Let α 2 (D) = max { | W | : W ⊆ V (D) and D[W] has no 2-cycle } be the α 2 (D) -stable number. In this paper, we show that every weakly connected digraph D with α 2 (D) = 2 has an antidirected Hamiltonian path. Secondly, we determine two families of well-characterized strongly connected digraphs H and M such that for any strongly connected digraph D ∈ H ∪ M which has no antidirected Hamiltonian cycle. And finally, we further prove that every strongly connected digraph D with α 2 (D) = 2 has an antidirected Hamiltonian cycle if and only if |V(D)| is even and D ∉ H ∪ M . [ABSTRACT FROM AUTHOR]

A graph is called supereulerian if it has a spanning eulerian subgraph. A connected even [2, 2s]-factor of a graph G is a connected factor with all vertices of even degree i (i ∈ { 2 , 4 , … , 2 s }) , where s ≥ 1 is an integer. Let W s , t be the graph obtained from vertex-disjoint s K 2 and (t + 1) K 1 by adding all possible edges between exactly one K 1 and the remaining graphs s K 2 and t K 1 . When s = t = 1 , W 1 , 1 is Z 1 . In this paper, we show that for any positive integer k ≤ 4 and 2 ≤ i ≤ k + 1 , every connected supereulerian H -free graph of order at least 6 contains a connected even [2, 2k]-factor if and only if H satisfies the following condition. H ≼ { { K 1 , 2 k + 2 , Z 1 } , { K 1 , k + i , W k + 3 - i , 0 } , { K 1 , k + i , W k + 2 - i , i - 1 } }. And when k = 5 , 6 , we give some relevant results. We also show that for positive integers k, 2 ≤ i ≤ k + 1 and H ≼ { { K 1 , 2 k + 2 , Z 1 } , { K 1 , k + i , W k + 3 - i , 0 } } , if G is supereulerian H -free graph of order at least 6, then G contains a connected even [2, 2k]-factor. Our results extend the result of Yang et al. (Discrete Appl Math 288:192–200, 2021) and Duan et al. (Ars Comb 115:385–389, 2014). [ABSTRACT FROM AUTHOR]

Solving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modification. Dynamic algorithms have been considered for several graph properties, for example connectivity, shortest paths and graph recognition. In this paper we present fully dynamic algorithms for the recognition of threshold graphs and chain graphs, which are optimal in the sense that the costs per modification are linear in the number of modified edges. Furthermore, our algorithms also consider the addition and deletion of sets of vertices as well as edges. In the negative case, i.e., where the graph is not a threshold graph or chain graph anymore, our algorithms return a certificate of constant size. Additionally, we present optimal fully dynamic algorithms for the Hamiltonian cycle problem and the Hamiltonian path problem on threshold and chain graphs which return a vertex cutset as certificate for the non-existence of such a path or cycle in the negative case. [ABSTRACT FROM AUTHOR]

For 0 ≤ ℓ < k , a Hamilton ℓ -cycle in a k-uniform hypergraph H is a cyclic ordering of the vertices of H in which the edges are segments of length k and every two consecutive edges overlap in exactly ℓ vertices. We show that for all 0 ≤ ℓ < k - 1 , every k-graph with minimum co-degree δ n with δ > 1 / 2 has (asymptotically and up to a subexponential factor) at least as many Hamilton ℓ -cycles as a typical random k-graph with edge-probability δ . This significantly improves a recent result of Glock, Gould, Joos, Kühn and Osthus, and verifies a conjecture of Ferber, Krivelevich and Sudakov for all values 0 ≤ ℓ < k - 1 . [ABSTRACT FROM AUTHOR]

For a finite group G, and a subset S of G (possibly, contains the identity element), the bi-Cayley graph Bcay(G, S) of G with respect to S is defined as the undirected bipartite graph with vertex set G × { 0 , 1 } and edge set { { (g , 0) , (g s , 1) } | g ∈ G , s ∈ S } . In this paper, we give some sufficient conditions for the existence of hamiltonian cycle in Bcay (G = Z m ⋊ H , S) , where G = Z m ⋊ H is a semiproduct of Zm by a subgroup H of G. In addition, we introduce a new graph operation, which produces some classes of bi-Cayley graphs having hamiltonian cycle. [ABSTRACT FROM AUTHOR]

Clearly, having a 2-factor in a graph is a necessary condition for a graph to be hamiltonian, while having an even factor in graph is a necessary condition for a graph to have a 2-factor. In this paper, we completely characterize the forbidden subgraph and pairs of forbidden subgraphs that force a 2-connected graph admitting a 2-factor (a necessary condition) to be hamiltonian and a connected graph with an even factor (a necessary condition) to have a 2-factor, respectively. Our results show that these pairs of forbidden subgraphs become wider than those in Faudree, Gould and in Fujisawa, Saito, respectively, if we impose the two necessary conditions, respectively.

The Hamiltonian path and cycle problems are well-known NP-complete problems. A given graph is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices and is Hamiltonian if it has a Hamiltonian cycle. In this paper, we show that every 3-connected solid supergrid graph is Hamiltonian-connected and every 2-connected solid supergrid graph is Hamiltonian, and give linear-time algorithms for computing Hamiltonian cycles and paths in these graphs. [ABSTRACT FROM AUTHOR]

A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.

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]

The non-zero component union graph Γ V B with respect to basis α 1 , α 2 , ⋯ , α n as S B = α i a i : a i ≠ 0 and α i ∈ V such that a ∼ b if S B a ∪ S B b = B . We establish some of the results about book thickness, Hamiltonian of the non-zero component union graph and also the planar, toroidal graphs with dim (Γ V B) = n m of the non-zero component union graphs of the finite dimensional vector space. [ABSTRACT FROM AUTHOR]

Let K n denote a complete graph on n vertices, where n is even. In recent works, geometric methods (finite projective planes, regular gons in the Euclidean plane) have been developed in the study of one-factorizations of K n , but a geometric viewpoint for perfect one-factorizations still remains unknown. In this note we apply the Lee metric to construct a one-factorization of K 2 p for an odd number p, which is isomorphic to those factorizations by Anderson and by Nakamura. Moreover, this construction is perfect for an odd prime p. By combining our approach with previous results, some known maximum distance separable codes in the Hamming space can be derived from the Lee metric. [ABSTRACT FROM AUTHOR]

We show that 3-graphs on n vertices whose minimum codegree is at least (2 / 3 + o (1)) n can be decomposed into tight cycles and admit Euler tours, subject to the trivial necessary divisibility conditions. We also provide a construction showing that our bounds are best possible up to a o(1) term. All together, our results answer negatively some recent questions of Glock, Joos, Kühn, and Osthus. [ABSTRACT FROM AUTHOR]

Let G be a simple graph and I (X G) = φ − 1 (x i 2 − x j 2 : i , j ∈ V G) , where φ : K [ E G ] → K [ V G ] is the homomorphism that sends an edge to the product of its vertices. The ideal I (X G) is Cohen–Macaulay, one-dimensional and binomial. If G is bipartite, it is known that the Castelnuovo–Mumford regularity of I (X G) is equal to the maximum cardinality of a set of edges having no more than half of the edges of any Eulerian subgraph of G. Here, with respect to the grevlex order associated to an ordering of the edge set of G, we describe a Gröbner basis for I (X G) , and we characterize the standard monomials of the ideal (I (X G) , t e) in terms of even sets of vertices marked with a parity. Using these results, we give a combinatorial interpretation of the degree of I (X G) , via the set of even sets of vertices of G; and we show that the Castelnuovo–Mumford regularity of I (X G) , for any graph, is the maximum cardinality of a set of edges having no more than half of the edges of any even Eulerian subgraph of G or, equivalently, the maximum cardinality of a minimum fixed parity T-join. [ABSTRACT FROM AUTHOR]