Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

Almost claw-free graphs

We say that G is almost claw-free if the vertices that are centers of induced claws (K_1,3) in G are independent and their neighborhoods are 2-dominated. Clearly, every claw-free graph is almost claw-free. It is shown that (i) every even connected almost claw-free graph has a perfect matching and (ii) every nontrivial locally connected K_1,4-free almost claw-free graph is fully cycle extendable.     

Greatest common divisors and least common multiples of graphs

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG ₁ andG ₂ ifG is a graph of maximum size for whichG|G ₁ andG|G ₂, while a graphH without isolated vertices is a least common multiple ofG ₁ andG ₂ ifH is a graph of minimum size for whichG ₁|H andG ₂|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG ₁ andG ₂ to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG ₁,G ₂ of graphs are determined, including when one ofG ₁ andG ₂ is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060     

Randomly matchable graphs

A graph is defined to be randomly matchable if every matching of G can be extended to a perfect matching. It is shown that the connected randomly matchable graphs are precisely K_2n and K_n,n (n ≥ 1).     

A class of planar well-covered graphs with girth four

A well-covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1-well-covered graph was introduced by Staples in her 1975 dissertation: a well-covered graph G is 1-well-covered if and only if G - v is also well covered for every point v in G. Except for K₂ and C₅, every 1-well-covered graph contains triangles or 4-cycles. We show that all planar 1-well-covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1995 John Wiley & Sons, Inc.     

Hamiltonian cycles in n‐extendable graphs

A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy deg_G x+deg_G y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002     

On some subclasses of well-covered graphs

A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the W_n property: For a positive integer n, a graph G belongs to class W_n if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W_n graphs containing arbitrarily large independent sets. A characterization of W_n graphs in terms of well-covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W_n graphs.     

Automorphisms of finite groups of bounded rank

LetG be a finite group admitting an automorphismα withm fixed points. Suppose every subgroup ofG isr-generated. It is shown that (1)G has a characteristic soluble subgroupH whose index is bounded in terms ofm andr, and (2) if the orders ofα andG are coprime, then the derived length ofH is also bounded in terms ofm andr. To Professor John Thompson, in honor of his outstanding achievements     

Rank of maximum matchings in a graph

The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG. We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings.     

On resolvable tree-decompositions of complete graphs

A partition of the edge set of a graph H into subsets inducing graphs H₁,…,H_s isomorphic to a graph G is said to be a G-decomposition of H. A G-decomposition of H is resolvable if the set {H₁,…,H_s} can be partitioned into subsets, called resolution classes, such that each vertex of H occurs precisely once in each resolution class. We prove that for every graceful tree T of odd order the obvious necessary conditions for the existence of a resolvable T-decomposition of a complete graph are asymptotically sufficient. This generalizes the results of Horton and Huang concerning paths and stars.     

Matching extension in the powers of n-connected graphs

Let G be a graph on p vertices. Then for a positive integer n₁ G is said to be n-extendible if (i) n < p/2, (ii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is n-connected, then G^k is -extendible for every integer k ≥ 2 such that . © 1996 John Wiley & Sons, Inc.     

Edge-clique graphs

The edge-clique graphK(G) of a graphG is that graph whose vertices correspond to the edges ofG and where two vertices ofK(G) are adjacent whenever the corresponding edges ofG belong to a common clique. It is shown that every edge-clique graph is a clique graph, and that ifG is either an interval graph or a line graph, then so too isK(G). An algorithm is provided for determining whether a graph is an edge-clique graph. A new graph called the STP graph is introduced and a relationship involving this graph, the edge-clique graph, and the line graph is presented. The STP graphs are also characterized.Research supported in part by Office of Naval Research Contract N00014-88-K-0018.Research supported in part by Office of Naval Research Contract N00014-88-K-0163.     

Excluding Induced Subdivisions of the Bull and Related Graphs

For any graph H, let Forb*(H) be the class of graphs with no induced subdivision of H. It was conjectured in [J Graph Theory, 24 (1997), 297–311] that, for every graph H, there is a function f_H: ?→? such that for every graph G∈Forb*(H), χ(G)≤f_H(ω(G)). We prove this conjecture for several graphs H, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex‐disjoint pendant edges), and what we call a “necklace,” that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:49–68, 2012     

Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W₄, bull}-free, both superclasses of triangle-free graphs.     

On kernels in perfect graphs

A kernel of a digraphD is a set of vertices which is both independent and absorbant. In 1983, C. Berge and P. Duchet conjectured that an undirected graphG is perfect if and only if the following condition is fulfilled: ifD is an orientation ofG (where pairs of opposite arcs are allowed) and if every clique ofD has a kernel thenD has a kernel. We prove here the conjecture for the complements of strongly perfect graphs and establish that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Orientation distance graphs

For two nonisomorphic orientations D and D′ of a graph G, the orientation distance d_o(D,D′) between D and D′ is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D′. The orientation distance graph 𝒟_o(G) of G has the set 𝒪(G) of pairwise nonisomorphic orientations of G as its vertex set and two vertices D and D′ of 𝒟₀(G) are adjacent if and only if d_o(D,D′) = 1. For a nonempty subset S of 𝒪(G), the orientation distance graph 𝒟₀(S) of S is the induced subgraph 〈S〉 of 𝒟_o(G). A graph H is an orientation distance graph if there exists a graph G and a set S⊆ 𝒪(G) such that 𝒟_o(S) is isomorphic to H. In this case, H is said to be an orientation distance graph with respect to G. This paper deals primarily with orientation distance graphs with respect to paths. For every integer n ≥ 4, it is shown that 𝒟_o(P_n) is Hamiltonian if and only if n is even. Also, the orientation distance graph of a path of odd order is bipartite. Furthermore, every tree is an orientation distance graph with respect to some path, as is every cycle, and for n ≥ 3 the clique number of 𝒟_o(P_n) is 2 if n is odd and is 3 otherwise. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 230–241, 2001     

Perfect Matchings in Total Domination Critical Graphs

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3 _t EC graph is a total domination edge-critical graph with total domination number 3 and a 3 _t VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G − v has a perfect matching for every vertex v in G. In this paper, we show that every 3 _t EC graph of even order has a perfect matching, while every 3 _t EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3 _t VC graph of even order that is K _1,7-free has a perfect matching, while every 3 _t VC graph of odd order that is K _1,6-free is factor-critical. We show that these results are tight in the sense that there exist 3 _t VC graphs of even order with no perfect matching that are K _1,8-free and 3 _t VC graphs of odd order that are K _1,7-free but not factor-critical.     

Noncyclic Graph of a Group

We associate a graph Γ _G to a nonlocally cyclic group G (called the noncyclic graph of G) as follows: take G\ Cyc(G) as vertex set, where Cyc(G) = {x ? G| 〈x, y〉 is cyclic for all y ? G}, and join two vertices if they do not generate a cyclic subgroup. We study the properties of this graph and we establish some graph theoretical properties (such as regularity) of this graph in terms of the group ones. We prove that the clique number of Γ _G is finite if and only if Γ _G has no infinite clique. We prove that if G is a finite nilpotent group and H is a group with Γ _G  ? Γ _H and |Cyc(G)| = |Cyc(H)| = 1, then H is a finite nilpotent group. We give some examples of groups G whose noncyclic graphs are “unique”, i.e., if Γ _G  ? Γ _H for some group H, then G ? H. In view of these examples, we conjecture that every finite nonabelian simple group has a unique noncyclic graph. Also we give some examples of finite noncyclic groups G with the property that if Γ _G  ? Γ _H for some group H, then |G| = |H|. These suggest the question whether the latter property holds for all finite noncyclic groups.     

Induced Matching Extendable Graph Powers

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. We obtain the following two results which give positive answers to two conjectures of Yuan. Result 1. If a connected graph G with |V(G)| even is locally connected, then G² is strongly IM-extendable. Result 2. If G is a 2-connected graph with |V(G)| even, then G³ is strongly IM-extendable. Research Supported by NSFC Fund 10371102.