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     

Edge sets contained in circuits

A graphG withn vertices has propertyp(r, s) ifG contains a path of lengthr and if every such path is contained in a circuit of lengths. G. A. Dirac and C. Thomassen [Math. Ann.203 (1973), 65–75] determined graphs with propertyp(r,r+1). We determine the least number of edges in a graphG in order to insure thatG has propertyp(r,s), we determine the least number of edges possible in a connected graph with propertyp(r,s) forr=1 and alls, forr=k ands=k+2 whenk=2, 3, 4, and we give bounds in other cases. Some resulting extremal graphs are determined. We also consider a generalization of propertyp(2,s) in which it is required that each pair of edges is contained in a circuit of lengths. Some cases of this last property have been treated previously by U. S. R. Murty [inProof Techniques in Graph Theory, ed. F. Harary, Academic Press, New York, 1969, pp. 111–118].     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

On dimensional properties of graphs

A dimensional property of graphs is a propertyP such that every graphG is the intersection of graphs having propertyP. IfP is a dimensional property, we describe a general method for computing the least integerk so thatG is the intersection ofk graphs having propertyP. We give simple applications of the method to computing the boxicity, the cubicity, the circular dimension, the rigid circuit dimension, and the overlap dimension, and mention connections to other concepts such as the threshold dimension.     

The class reconstruction number of maximal planar graphs

The reconstruction numberrn(G) of a graphG was introduced by Harary and Plantholt as the smallest number of vertex-deleted subgraphsG _i =G – v _i in the deck ofG which do not all appear in the deck of any other graph. For any graph theoretic propertyP, Harary defined theP-reconstruction number of a graph G P as the smallest number of theG _i in the deck ofG, which do not all appear in the deck of any other graph inP We now study the maximal planar graph reconstruction numberrn(G), proving that its value is either 1 or 2 and characterizing those with value 1.     

Hereditary modular graphs

In a hereditary modular graphG, for any three verticesu, v, w of an isometric subgraph ofG, there exists a vertex of this subgraph that is simultaneously on some shortestu, v-path,u, w-path andv, w-path. It is shown that the hereditary modular graphs are precisely those bipartite graphs which do not contain any isometric cycle of length greater than four. There is a polynomial-time algorithm available which decides whether a given (bipartite) graph is hereditary modular or not. Finally, the chordal bipartite graphs are characterized by forbidden isometric subgraphs.     

Edge covering coloring of nearly bipartite graphs

LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′_c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′_c(G) ≤δ. If χ′_c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.     

Graph minors. I. Excluding a forest

The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG₁,…,G_r each of which has at mostk + 1 vertices, by identifying some vertices ofG_i pairwise with some ofG_i+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width?k. This, together with results of other papers, yields a “good” algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite.     

Relaxed chromatic numbers of graphs

Given any family of graphsP, theP chromatic number _p (G) of a graphG is the smallest number of classes into whichV(G) can be partitioned such that each class induces a subgraph inP. We study this for hereditary familiesP of two broad types: the graphs containing no subgraph of a fixed graphH, and the graphs that are disjoint unions of subgraphs ofH. We generalize results on ordinary chromatic number and we computeP chromatic number for special choices ofP on special classes of graphs.Research supported in part by ONR Grant N00014-85K0570 and by a grant from the University of Illinois Research Board.     

Isoperimetric numbers of graph bundles

The main aim of this paper is to give some upper and lower bounds for the isoperimetric numbers of graph coverings or graph bundles, with exact values in some special cases. In addition, we show that the isoperimetric number of any covering graph is not greater than that of the base graph. Mohar's theorem for the isoperimetric number of the cartesian product of a graph and a complete graph can be extended to a more general case: The isoperimetric numberi(G × K _2n) of the cartesian product of any graphG and a complete graphK _2n on even vertices is the minimum of the isoperimetric numberi(G) andn, and it is also a sharp lower bound of the isoperimetric numbers of all graph bundles over the graphG with fiberK _2n. Furthermore, ifn 2i(G) then the isoperimetric number of any graph bundle overG with fibreK _n is equal to the isoperimetric numberi(G) ofG. Partially supported by The Ministry of Education, Korea.     

Note on a conjecture of toft

A conjecture of Toft [17] asserts that any 4-critical graph (or equivalently, every 4-chromatic graph) contains a fully odd subdivision ofK ₄. We show that if a graphG has a degree three nodev such thatG-v is 3-colourable, then eitherG is 3-colourable or it contains a fully oddK ₄. This resolves Toft's conjecture in the special case where a 4-critical graph has a degree three node, which is in turn used to prove the conjecture for line-graphs. The proof is constructive and yields a polynomial algorithm which given a 3-degenerate graph either finds a 3-colouring or exhibits a subgraph that is a fully odd subdivision ofK ₄. (A graph is 3-degenerate if every subgraph has some node of degree at most three.)     

A surprising property of the least eigenvalue of a graph

Let λ(G) be the least eigenvalue of a graph G. A real number r has the induced subgraph property provided λ(G)<r implies G has an induced subgraph H with λ(H)=r. It is shown that the only numbers with the induced subgraph property are 0, ?1, ?$\text{2}$, and ?2.     

On the perfect orderability of unions of two graphs

A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P₄, 2K₂, and C₄ as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G₁ and G₂, then G is perfectly orderable whenever G₁ and G₂ are both P₄‐free and 2K₂‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: if G₁ and G₂ are two edge‐disjoint graphs that are P₄‐free and 2K₂‐free, then the union of G₁ and G₂ is perfectly orderable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000     

Minimal configuration bicyclic graphs

The nullity η(G) of a graph G is the multiplicity of zero as an eigenvalue of the adjacency matrix of G. If η(G)?=?1, then the core of G is the subgraph induced by the vertices associated with the nonzero entries of the kernel eigenvector. The set of vertices which are not in the core is the periphery of G. A graph G with nullity one is minimal configuration if no two vertices in the periphery are adjacent and deletion of any vertex in the periphery increases the nullity. An ∞-graph ∞(p,?l,?q) is a graph obtained by joining two vertex-disjoint cycles C _p and C _q by a path of length l?≥?0. Let ?* be the class of bicyclic graphs with an ∞-graph as an induced subgraph. In this article, we characterize the graphs in ?* which are minimal configurations.     

On regular bipartite-preserving supergraphs

For a graphG with chromatic numberχ(G) ? 2 and maximum degree Δ(G), there exists anr-regular graphH, for everyr ? Δ(G), such thatG is an induced subgraph ofH and_χ(H) =_χ (G). In the case whereG is bipartite, the minimum order of such a graphH is determined.     

Parabolic rectangle packings

The contacts graph (or nerve) of a packing is a combinatorial graph which describes the combinatorics of the packing. Let G be the 1-skeleton of a triangulation of an open disk and let P be a rectangle packing with contact graph G. In this paper a topological criterion for deciding whether G is an α-EL parabolic graph is given. Our result shows the internal relation between the topological property of the packing P and the combinatorial property of the contacts graph G of P.     

Graphs isomorphic to subgraphs of their iterated line graphs

A graphG is said to be embeddable into a graphH, if there is an isomorphism ofG into a subgraph ofH. It is shown in this paper that every unicycle or tree which is neither a path norK _1,3 embeds in itsn-th iterated line graph forn1 or 2, 3, and that every other connected graph that embeds in itsn-th iterated line graph may be constructed from such an embedded unicycle or tree in a natural way. A special kind of embedding of graph into itsn-th iterated line graph, called incidence embedding, is studied. Moreover, it is shown that for every positive integerk, there exists a graphG such that (G) = , where (G) is the leastn1 for whichG embeds inL ⁿ(G).     

How many random edges make a graph hamiltonian?

A threshold for a graph propertyQ in the scale of random graph spacesG _n,p is ap-band across which the asymptotic probability ofQ jumps from 0 to 1. We locate a sharp threshold for the property of having a hamiltonian path.     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

Path factors of bipartite graphs

A path on n vertices is denoted by P_n. For any graph H, the number of isolated vertices of H is denoted by i(H). Let G be a graph. A spanning subgraph F of G is called a {P₃, P₄, P₅}-factor of G if every component of F is one of P₃, P₄, and P₅. In this paper, we prove that a bipartite graph G has a {P₃, P₄, P₅}-factor if and only if i(G ? S ? M) ≦ 2|S| + |M| for all S ? V(G) and independent M ? E(G).