Hamiltonian groups are color-graph-hamiltonian

A group Γ is said to be color -graph -hamiltonian if Γ has a minimal generating set Δ such that the Cayley color graph D_Δ(Γ) is hamiltonian. It is shown that every hamiltonian group is color -graph -hamiltonian.     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

Dominating sets in n-cubes

A perfectdominatingset S of a graph Γ is a set of vertices of Γ such that every vertex of Γ is either in S or is adjacent to exactly one vertex of S. We show that a perfect dominating set of the n-cube Q_n induces a subgraph of Q_n whose components are isomorphic to hypercubes. We conjecture that each of these hypercubes has the same dimension. We then prove that if Q_r is a component of the subgraph induced by S, then n ? r ? 1 or 3 (mod 6). A number of examples are given and connections with Steiner Systems and codes are noted.     

Über Gruppen Von Iterativen Wurzeln Der Formalen Potenzreihe F(x) = x

Let ?¦x¦ be the ring of formal power series in one indeterminate x over ?, denote by Γ the group of invertible series in ?¦x¦, and by E_Γ the set of all iterative roots of x in Γ. Then we will show that E_Γ is neither a subgroup of Γ nor a family of commuting series. We describe all subgroups of Γ lying in E_Γ, they are abelian and isomorphic to subgroups of the group E of complex roots of unity. Furthermore we determine the maximal subgroups of Γ in E{Γ} and use them to investigate how the subgroups in E _I are related.     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

On the hamiltonian path graph of a graph

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and v are adjacent if and only if F contains a hamiltonian u ? v path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that K?_d ? H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with at least five vertices is at least |V(F)| + t(t ? 0), then H(F) contains a complete subgraph of order t + 4.     

On hamiltonian cycles in the prism over the odd graphs

The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph O_k is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that O_k is hamiltonian for all k>2. We show that the prism over O_k is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011     

Hamilton cycles in prisms

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If G is hamiltonian, then G□K₂ is also hamiltonian but the converse does not hold in general. Having a hamiltonian prism is shown to be an interesting relaxation of being hamiltonian. In this article, we examine classical problems on hamiltonicity of graphs in the context of having a hamiltonian prism. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 249–269, 2007     

Strong difference families over arbitrary graphs

The concept of a strong difference family formally introduced in Buratti [J Combin Designs 7 (1999), 406–425] with the aim of getting group divisible designs with an automorphism group acting regularly on the points, is here extended for getting, more generally, sharply‐vertex‐transitive Γ‐decompositions of a complete multipartite graph for several kinds of graphs Γ. We show, for instance, that if Γ has e edges, then it is often possible to get a sharply‐vertex‐transitive Γ‐decomposition of K_{m × e} for any integer m whose prime factors are not smaller than the chromatic number of Γ. This is proved to be true whenever Γ admits an α‐labeling and, also, when Γ is an odd cycle or the Petersen graph or the prism T₅ or the wheel W₆. We also show that sometimes strong difference families lead to regular Γ‐decompositions of a complete graph. We construct, for instance, a regular cube‐decomposition of K_16m for any integer m whose prime factors are all congruent to 1 modulo 6. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 443–461, 2008     

Prism‐hamiltonicity of triangulations

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If the prism over G is hamiltonian, we say that G is prism‐hamiltonian. We prove that triangulations of the plane, projective plane, torus, and Klein bottle are prism‐hamiltonian. We additionally show that every 4‐connected triangulation of a surface with sufficiently large representativity is prism‐hamiltonian, and that every 3‐connected planar bipartite graph is prism‐hamiltonian. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 181–197, 2008     

An improvement of fraisse's sufficient condition for hamiltonian graphs

Let G be a k-connected graph of order n. For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S. We prove that if there exists some s, 1 ≤ s ≤ k, such that Σ_xiEX d(X\{X_i}) > s(n?1) – k[s/2] – i(X)[(s?1)/2] holds for every independetn set X ={x₀, x₁ ?x_s} of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries.     

Polar boundary sets for superdiffusions and removable lateral singularities for nonlinear parabolic PDEs

Suppose L is a second-order elliptic differential operator in ℝ^d and D is a bounded, smooth domain in ℝ^d. Let 1 < α ≤ 2 and let Γ be a closed subset of ∂D. It is known [13] that the following three properties are equivalent: (α) Γ is ∂-polar; that is, Γ is not hit by the range of the corresponding (L, α)-superdiffusion in D; (β) the Poisson capacity of Γ is equal to 0; that is, the integral is equal to 0 or ∞ for every measure ν, where ρ(x) is the distance to the boundary and k(x, y) is the corresponding Poisson kernel; and (γ) Γ is a removable boundary singularity for the equation Lu = u^α in D; that is, if u ≥ 0 and Lu = u^α in D and if u = 0 on ∂D \ Γ, then u = 0. We investigate a similar problem for a parabolic operator in a smooth cylinder 𝒬 = ℝ₊ × D. Let Γ be a compact set on the lateral boundary of 𝒬. We show that the following three properties are equivalent: (a) Γ is 𝒢-polar; that is, Γ is not hit by the graph of the corresponding (L, α)-superdiffusion in 𝒬; (b) the Poisson capacity of Γ is equal to 0; that is, the integral is equal to 0 or ∞ for every measure ν, where k(r, x; t, y) is the corresponding (parabolic) Poisson kernel; and (c) Γ is a removable lateral singularity for the equation u˙ + Lu = u^α in 𝒬; that is, if u ≥ 0 and u˙ + Lu = u^α in 𝒬 and if u = 0 on ∂𝒬 \ Γ and on {∞} × D, then u = 0. © 1998 John Wiley & Sons, Inc.     

Group labelings of graphs

Given a graph Γ an abelian group G, and a labeling of the vertices of Γ with elements of G, necessary and sufficient conditions are stated for the existence of a labeling of the edges in which the label of each vertex equals the product of the labels of its incident edges. Such an edge labeling is called compatible. For vertex labelings satisfying these conditions, the set of compatible edge labelings is enumerated.     

The embedding of the components of the auslander-reiten quiver of an artin algebra containing no oriented cycle 1

Let Abe an artin algebra. Let Γ be a component of the Auslander-Reiten Quiver Γ _A and Γ contain no oriented cycle. If Γ is stable or semi-stable, then the structure of Γ is known. Here, we are going to consider general component which may contain both injective vertices and projective vertices at the same time. We will show that Γ can be embedded in some Δ with Δ isomorphic to a section of Γ if and only if every possible path from an injective vertex to a projective vertex is sectional. This result generalizes part of Zhang’s theorem and the corresponding part of Liu’s theorem.     

Stability,domination and irredundance in a graph

In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V – X is joined to at least one vertex of X. A set X is called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that is a vertex of V – X joined to it but to no other vertex of X. Let α′ and α, γ, and Γ, ir and IR, denote respectively the minimum and maximum cardinalities of a maximal stable set, a minimal dominating set, and a maximal irredundant set. It is known that ir ? γ ? α′ ? α ? Γ ? IR and that if G does not contain any induced subgraph isomorphic to K_1,3, then γ = α′. Here we prove that if G contains no induced subgraph isomorphic to K_1,3 or to the graph H of figure 1, then ir = γ = α′. We prove also that if G contains no induced subgraph isomorphic to K_1,3, to H, or to the graph h of figure 3, then Γ = IR. Finally, we improve a result of Bollobas and Cockayne about sufficient conditions for γ = ir in terms of forbidden subgraphs.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Nowhere‐zero 3‐flows in products of graphs

A graph G is an odd‐circuit tree if every block of G is an odd length circuit. It is proved in this paper that the product of every pair of graphs G and H admits a nowhere‐zero 3‐flow unless G is an odd‐circuit tree and H has a bridge. This theorem is a partial result to the Tutte's 3‐flow conjecture and generalizes a result by Imrich and Skrekovski [7] that the product of two bipartite graphs admits a nowhere‐zero 3‐flow. A byproduct of this theorem is that every bridgeless Cayley graph G = Cay(Γ,S) on an abelian group Γ with a minimal generating set S admits a nowhere‐zero 3‐flow except for odd prisms. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Group Gradings on G 2

In this article, we describe all group gradings by a finite abelian group Γ of a simple Lie algebra of type G ₂ over an algebraically closed field F of characteristic zero.     

Semigroup Rings as Weakly Factorial Domains

Let D be an integral domain, Γ be a torsion-free grading monoid with quotient group G, and D[Γ] be the semigroup ring of Γ over D. We show that if G is of type (0, 0, 0,…), then D[Γ] is a weakly factorial domain if and only if D is a weakly factorial GCD-domain and Γ is a weakly factorial GCD-semigroup. Let ? be the field of real numbers and Γ be the additive semigroup of nonnegative rational numbers. We also show that Γ is a weakly factorial GCD-semigroup, but ?[Γ] is not a weakly factorial domain.