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.     

Retract-collapsible graphs and invariant subgraph properties

A (finite or infinite) graph G is retract-collapsible if it can be dismantled by deleting systematically at each step every vertex that is strictly dominated, in such a way that the remaining subgraph is a retract of G, and so as to get a simplex at the end. A graph is subretract-collapsible if some graph obtained by planting some rayless tree at each of its vertices is retract-collapsible. It is shown that the subretract-colapsible graphs are cop-win; and that a ball-Helly graph is subretract-collapsible if and only if it has no isometric infinite paths (thus in particular if it has no infinite paths, or if it is bounded). Several fixed subgraph properties are proved. In particular, if G is a subretract-collapsible graph, and f a contraction from G into G, then (i) if G has no infinite simplices, then f(S) = S for some simplex S of G; and (ii) if the dismantling of G can be achieved in a finite number of steps and if some family of simplices of G has a compacity property, then there is a simplex S of G such that f(S) ? S. This last result generalizes a property of bounded ball-Helly graphs. © 1995 John Wiley & Sons, Inc.     

Maximal sets of hamilton cycles in complete multipartite graphs

A set S of edge‐disjoint hamilton cycles in a graph G is said to be maximal if the edges in the hamilton cycles in S induce a subgraph H of G such that G ? E(H) contains no hamilton cycles. In this context, the spectrum S(G) of a graph G is the set of integers m such that G contains a maximal set of m edge‐disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs and for all complete bipartite graphs. In this paper, we extend these results to the complete multipartite graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 49–66, 2003     

Subdivision Extendibility

Let H be a multigraph and G a graph containing a subgraph isomorphic to a subdivision of H, with S ⊂ V(G) (the ground set) the image of V(H) under the isomorphism. We consider connectivity and minimum degree or degree sum conditions sufficient to imply there is a spanning subgraph of G isomorphic to a subdivision of H on the same ground set S. These results generalize a number of theorems in the literature.     

Set domination in graphs

Let G = (V, E) be a connected graph. A set D ? V is a set-dominating set (sd-set) if for every set T ? V ? D, there exists a nonempty set S ? D such that the subgraph 〈S ∪ T〉 induced by S ∪ T is connected. The set-domination number γ_s(G) of G is the minimum cardinality of a sd-set. In this paper we develop properties of this new parameter and relate it to some other known domination parameters.     

Graphs with given group and given constant link

A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link .L Sabidussi proved that for any finite group F and any n ? 3 there are infinitely many n-regular connected graphs G with AutG ? Γ. We will prove a stronger result: For any finite group Γ and any link graph L with at least one isolated vertex and at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ.     

A degree condition for spanning eulerian subgraphs

Let p ≥ 2 be a fixed integer. Let G be a simple and 2-edge-connected graph on n vertices, and let g be the girth of G. If d(u) + d(v) ≥ (2/(g ? 2))((n/p) ? 4 + g) holds whenever uv ? E(G), and if n is sufficiently large compared to p, then either G has a spanning eulerian subgraph or G can be contracted to a graph G₁ of order at most p without a spanning eulerian subgraph. Furthermore, we characterize the graphs that satisfy the conditions above such that G₁ has order p and does not have any spanning eulerian subgraph. © 1993 John Wiley & Sons, Inc.     

Representing groups by graphs with constant link and hypergraphs

A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link L. We prove that for any finite group Γ and any disconnected link graph L with at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ. We look at the analogous problem for connected link graphs, namely, link graphs that are paths or have disconnected complements. Furthermore we prove that for n, r ≥ 2, but not n = 2 = r, any finite group can be represented by infinitely many connected r-uniform, n-regular hypergraphs of arbitrarily large girth.     

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.     

Long cycles in subgraphs of (pseudo)random directed graphs

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant c = c(γ) such that the following holds. Let G = (V, E) be a (pseudo)random directed graph on n vertices and with at least a linear number of edges, and let G′ be a subgraph of G with (1/2 + γ)|E| edges. Then G′ contains a directed cycle of length at least (c ? o(1))n. Moreover, there is a subgraph G′′of G with (1/2 + γ ? o(1))|E| edges that does not contain a cycle of length at least cn. © 2011 Wiley Periodicals, Inc. J Graph Theory 70: 284–296, 2012     

Vertex‐transitive graphs that remain connected after failure of a vertex and its neighbors

A d‐regular graph is said to be superconnected if any disconnecting subset with cardinality at most d is formed by the neighbors of some vertex. A superconnected graph that remains connected after the failure of a vertex and its neighbors will be called vosperian. Let Γ be a vertex‐transitive graph of degree d with order at least d+4. We give necessary and sufficient conditions for the vosperianity of Γ. Moreover, assuming that distinct vertices have distinct neighbors, we show that Γ is vosperian if and only if it is superconnected. Let G be a group and let S?G\{1} with S=S^?1. We show that the Cayley graph, Cay(G, S), defined on G by S is vosperian if and only if G\(S∪{1}) is not a progression and for every non‐trivial subgroup H and every a∈G, If moreover S is aperiodic, then Cay(G, S) is vosperian if and only if it is superconnected. © 2011 Wiley Periodicals, Inc. J Graph Theory 67:124‐138, 2011     

A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees

Let G be a connected simple graph, let X?V (^G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d _T (x) for all x ∈ X, where d _T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d _T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N _G (S) ? S| ? f(S) + 2|S| ? ω _G (S) ≥, where ω _G (S) is the number of components of the subgraph induced by S.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

Two-Connected Augmentation Problems in Planar Graphs

Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting subgraph satisfies specified (edge or vertex) connectivity requirements between pairs of nodes of S. This has important applications in upgrading telecommunication networks to be invulnerable to link or node failures. We give a polynomial algorithm for this problem when S is connected, nodes are required to be at most 2-connected, and G is planar. Applications to network design and multicommodity cut problems are also discussed.     

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.     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

H-domination in graphs

Let H be some fixed graph of order p. For a given graph G and vertex set S⊆V(G), we say that S is H-decomposable if S can be partitioned as S=S₁∪S₂∪?∪S_j where, for each of the disjoint subsets S_i, with 1?i?j, we have |S_i|=p and H is a spanning subgraph of 〈S_i〉, the subgraph induced by S_i. We define the H-domination number of G, denoted as γ_H(G), to be the minimum cardinality of an H-decomposable dominating set S. If no such dominating set exists, we write γ_H(G)=∞. We show that the associated H-domination decision problem is NP-complete for every choice of H. Bounds are shown for γ_H(G). We show, in particular, that if δ(G)?2, then γ_P3(G)?3γ(G). Also, if γ_P3(G)=3γ(G), then every γ(G)-set is an efficient dominating set.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

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.     

Cochromatic Number and the Genus of a Graph

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G. In this paper we introduce the problem of determining for a surface S, z(S), which is the maximum cochromatic number among all graphs G that embed in S. Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z(S) is nonorientable of genus at least four, then z(S)≤χ(S). Here χ(S) denotes the chromatic number S. Exact results are obtained for the sphere, the Klein bottle, and for S. It is conjectured that z(S) is equal to the maximum n for which the graph G_n = K₁ ∪ K₂ ∪ … ∪ K_n embeds in S.