Tutte sets in graphs I: Maximal tutte sets and D‐graphs

A well‐known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency of G. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. In this article, we study the structural aspects of maximal Tutte sets in a graph G. Towards this end, we introduce a related graph D(G). We first show that the maximal Tutte sets in G are precisely the maximal independent sets in its D‐graph D(G), and then continue with the study of D‐graphs in their own right, and of iterated D‐graphs. We show that G is isomorphic to a spanning subgraph of D(G), and characterize the graphs for which G?D(G) and for which D(G)?D²(G). Surprisingly, it turns out that for every graph G with a perfect matching, D³(G)?D²(G). Finally, we characterize bipartite D‐graphs and comment on the problem of characterizing D‐graphs in general. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 343–358, 2007     

Iterating the branching operation on a directed graph

The branching operation D, defined by Propp, assigns to any directed graph G another directed graph D(G) whose vertices are the oriented rooted spanning trees of the original graph G. We characterize the directed graphs G for which the sequence δ(G) = (G, D(G), D²(G),…) converges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connected directed graphs G, δ(G) converges if and only if D²(G) = D(G). © 1997 John Wiley & Sons, Inc.     

A Generalization of the Gallai–Roy Theorem

 A well-known and essential result due to Roy ([4], 1967) and independently to Gallai ([3], 1968) is that if D is a digraph with chromatic number χ(D), then D contains a directed path of at least χ(D) vertices. We generalize this result by showing that if ψ(D) is the minimum value of the number of the vertices in a longest directed path starting from a vertex that is connected to every vertex of D, then χ(D) ≤ψ(D). For graphs, we give a positive answer to the following question of Fajtlowicz: if G is a graph with chromatic number χ(G), then for any proper coloring of G of χ(G) colors and for any vertex v∈V(G), there is a path P starting at v which represents all χ(G) colors. Received: May 20, 1999 Final version received: December 24, 1999     

Hadwiger number and chromatic number for near regular degree sequences

We consider a problem related to Hadwiger's Conjecture. Let D=(d₁, d₂, …, d_n) be a graphic sequence with 0?d₁?d₂?···?d_n?n?1. Any simple graph G with D its degree sequence is called a realization of D. Let R[D] denote the set of all realizations of D. Define h(D)=max{h(G): G∈R[D]} and χ(D)=max{χ(G): G∈R[D]}, where h(G) and χ(G) are Hadwiger number and chromatic number of a graph G, respectively. Hadwiger's Conjecture implies that h(D)?χ(D). In this paper, we establish the above inequality for near regular degree sequences. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 175–183, 2010     

Total outer-connected domination numbers of trees

Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a total dominating set if D is dominating, and the induced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total dominating set of G. A set DV(G) is a total outer-connected dominating set if D is total dominating, and the induced subgraph G[V(G)−D] is a connected graph. The total outer-connected domination number of G is the minimum cardinality of a total outer-connected dominating set of G. We characterize trees with equal total domination and total outer-connected domination numbers. We give a lower bound for the total outer-connected domination number of trees and we characterize the extremal trees.     

On Hypercentral Groups G With |G:G n |<∞

In 1960, Baumslag, following up on work of Cernikov for the 1940s, proved that a hypercentral p-group G with G = G ^p is a divisible Abelian group. In this article, we provide an interesting generalization of this 45 year old result: If a hypercentral p-group G satisfies |G:G ^p |<∞ (of course, it contains G = G ^p ), there exists a normal divisible Abelian subgroup D such that |G:D|<∞.     

On graphs determining links with maximal number of components via medial construction

Let G be a connected plane graph, D(G) be the corresponding link diagram via medial construction, and μ(D(G)) be the number of components of the link diagram D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1, where n(G) is the nullity of G. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K₁ by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs.     

Sharp bounds on distance spectral radius of graphs

Let D(G) denote the distance matrix of a connected graph G. The largest eigenvalue of D(G) is called the distance spectral radius of a graph G, denoted by ?(G). In this article, we give sharp upper and lower bounds for the distance spectral radius and characterize those graphs for which these bounds are best possible.     

Integral distance graphs

Suppose D is a subset of all positive integers. The distance graph G(Z, D) with distance set D is the graph with vertex set Z, and two vertices x and y are adjacent if and only if |x − y| ≡ D. This paper studies the chromatic number χ(Z, D) of G(Z, D). In particular, we prove that χ(Z, D) ≤ |D| + 1 when |D| is finite. Exact values of χ(G, D) are also determined for some D with |D| = 3. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 287–294, 1997     

Diameter increase caused by edge deletion

We consider the following problem: Given positive integers k and D, what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D, assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of (k + 1)D and a lower bound of (k + 1)D ? k for even D and of (k + 1)D ? 2k + 2 for odd D ? 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3D ? 1 and 4D ? 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ? 4 and k = 6, and k = 5 and k ? 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√k). For directed graphs G, the bounds depend strongly on D: for D = 1 and D = 2 we derive exact bounds of θ(√k) and of 2k + 2, respectively, while for D ? 3 the resulting diameter is in general unbounded in terms of k and D. Finally, we prove several related problems NP-complete.     

Irreducible Subgroups of GL 1(D) Satisfying Group Identities

ABSTRACT

Let D be a finite dimensional F -central division algebra and G an irreducible subgroup of D*: = GL ₁(D). Here we investigate the structure of D under various group identities on G. In particular, it is shown that when [D:F] = p ², p a prime, then D is cyclic if and only if D* contains a nonabelian subgroup satisfying a group identity.     

Bounds on the Distance Two-Domination Number of a Graph

 For a graph G = (V, E), a subset D⊆V(G) is said to be distance two-dominating set in G if for each vertex u∈V−D, there exists a vertex v∈D such that d(u,v)≤2. The minimum cardinality of a distance two-dominating set in G is called a distance two-domination number and is denoted by γ₂(G). In this note we obtain various upper bounds for γ₂(G) and characterize the classes of graphs attaining these bounds. Received: May 31, 1999 Final version received: July 13, 2000     

Connected -tuple twin domination in de Bruijn and Kautz digraphs

For a digraph G, a k-tuple twin dominating set D of G for some fixed k≥1 is a set of vertices such that every vertex is adjacent to at least k vertices in D, and also every vertex is adjacent from at least k vertices in D. If the subgraph of G induced by D is strongly connected, then D is called a connected k-tuple twin dominating set of G. In this paper, we give constructions of minimal connected k-tuple twin dominating sets for de Bruijn digraphs and Kautz digraphs.     

Real 2-Regular Classes and 2-Blocks

Suppose that G is a finite group. We show that every 2-block of G has a defect class which is real. As a partial converse, we show that if G has a real 2-regular class with defect group D and if N(D)/D has no dihedral subgroup of order 8, then G has a real 2-block with defect group D. More generally, we show that every 2-block of G which is weakly regular relative to some normal subgroup N has a defect class which is real and contained in N. We give several applications of these results and also investigate some consequences of the existence of non-real 2-blocks.     

The Canonical Genus of a Classical and Virtual Knot

A diagram D of a knot defines the corresponding Gauss Diagram G _D . However, not all Gauss diagrams correspond to the ordinary knot diagrams. From a Gauss diagram G we construct closed surfaces F _G and S _G in two different ways, and we show that if the Gauss diagram corresponds to an ordinary knot diagram D, then their genus is the genus of the canonical Seifert surface associated to D. Using these constructions we introduce the virtual canonical genus invariant of a virtual knot and find estimates on the number of alternating knots of given genus and given crossing number.     

Hamiltonicity and reversing arcs in digraphs

In this paper we introduce a new hamiltonian-like property of graphs. A graph G is said to be cyclable if for each orientation D of G there is a set S of vertices such that reversing all the arcs of D with one end in S results in a hamiltonian digraph. We characterize cyclable complete multipartite graphs and prove that the fourth power of any connected graph G with at least five vertices is cyclable. If, moreover, G is two-connected then its cube is cyclable. These results are shown to be best possible in a sense. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 13–30, 1998     

On minimal representations of Chevalley groups of type D n , E n and G 2

Let G be a simply connected Chevalley group of type D _n , E _n or G₂. In this paper, we show that the minimal representation of G is unique for types D _n and E _n and it does not exist for the type G₂.     

Clique-transversal sets in 4-regular claw-free graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by τ _c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.     

On the distributive radical of an Archimedean lattice-ordered group

Let G be an Archimedean ℓ-group. We denote by G ^d and R _D (G) the divisible hull of G and the distributive radical of G, respectively. In the present note we prove the relation (R _D (G)) ^d = R _D (G ^d ). As an application, we show that if G is Archimedean, then it is completely distributive if and only if it can be regularly embedded into a completely distributive vector lattice.     

Augmenting forests to meet odd diameter requirements

Given a graph G=(V,E) and an integer D≥1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P=NP. For a forest G and an odd D≥3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D; our algorithm delivers an 8-approximate solution in O(|V|³) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if the augmented graph is additionally required to be biconnected.