On the regulation number of a multigraph

The regulation number of a multigraphG having maximum degreed is the minimum number of additional vertices that are required to construct ad-regular supermultigraph ofG. It is shown that the regulation number of any multigraph is at most 3. The regulation number of a multidigraph is defined analogously and is shown never to exceed 2. A multigraphG has strengthm if every two distinct vertices ofG are joined by at mostm parallel edges. For a multigraphG of strengthm and maximum degreed, them-regulation number ofG is the minimum number of additional vertices that are required to construct ad-regular supermultigraph ofG having strengthm. A sharp upper bound on the 2-regulation number of a multigraph is shown to be (d+5)/2, and a conjecture for generalm is presented. Research supported by a Western Michigan University faculty research fellowship. Research Professor of Electrical Engineering and Computer Science, Stevens Institute, Hoboken, NJ and Visiting Scholar, Courant Institute, New York University, Spring 1984. Research supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.     

Disproof of a conjecture in graph reconstruction theory

In his thesis [3] B. D. Thatte conjectured that ifG=G ₁,G ₂,...G _n is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.This research was partially supported by Hungarian National Foundation of Scientific Research Grant no. 1812     

Isomorphic factorizations VIII: Bisectable trees

A tree is called even if its line set can be partitioned into two isomorphic subforests; it is bisectable if these forests are trees. The problem of deciding whether a given tree is even is known (Graham and Robinson) to be NP-hard. That for bisectability is now shown to have a polynomial time algorithm. This result is contained in the proof of a theorem which shows that if a treeS is bisectable then there is a unique treeT that accomplishes the bipartition. With the help of the uniqueness ofT and the observation that the bisection ofS into two copies ofT is unique up to isomorphism, we enumerate bisectable trees. Visiting Professor, University of Newcastle, 1976 and 1977 when this work was begun. Visiting Scholar, University of Michigan, 1981–82 on leave from Newcastle University (Australia) when this work was completed. The research was supported by grants from the Australian Research Grants Commission. The computing reported herein was performed by A. Nymeyer.     

Randomlyn-cyclic digraphs

A digraphD is randomlyn-cyclic (n≥3) if for each vertexv ofD, every (directed) path with initial vertexv and having length at mostn−1 can be extended to av−v (directed) cycle of lengthn. Several results related to and examples of randomlyn-cyclic digraphs are presented. Also, all randomlyn-cyclic digraphs forn=3, 4, and 5 are determined. Research supported by a Western Michigan University faculty research fellowship. Research supported in part by a College of Arts and Sciences and Graduate College research assistantship from Western Michigan University.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.     

Connected Domination Stable Graphs Upon Edge Addition

Abstract

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.     

Graphs with prescribed degree sets and girth

For a finite nonempty set of integers, each of which is at least two, and an integern 3, the numberf(;n) is defined as the least order of a graph having degree set and girthn. The numberf(;n) is evaluated for several sets and integersn. In particular, it is shown thatf({3, 4}; 5) = 13 andf({3, 4}; 6) = 18.Research of the third author was partially supported by a Faculty Research Fellowship from Western Michigan University.     

On Connected [g,f +1]-Factors in Graphs

Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G), and g and f two positive integral functions from V (G) to Z⁺-{1} such that g(v) ≤ f(v) ≤ d_G(v) for all v ∈V (G), where d_G(v) is the degree of the vertex v. It is shown that every graph G, including both a [g,f]-factor and a hamiltonian path, contains a connected [g,f +1]-factor. This result also extends Kano’s conjecture concerning the existence of connected [k,k+1]-factors in graphs. * The work of this author was supported by NSFC of China under Grant No. 10271065, No. 60373025. † The work of these authors was also supported in part by the US Department of Energy’s Genomes to Life program (http://doegenomestolife.org/) under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org) and by National Science Foundation (NSF/DBI-0354771,NSF/ITR-IIS-0407204).     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Proof of a Conjecture of Bollobás and Eldridge for Graphs of Maximum Degree Three*

Let G ₁ and G ₂ be simple graphs on n vertices. If there are edge-disjoint copies of G ₁ and G ₂ in K _n , then we say there is a packing of G ₁ and G ₂. A conjecture of Bollobás and Eldridge [5] asserts that if ((G ₁)+1) ((G ₂)+1) n + 1 then there is a packing of G ₁ and G ₂. We prove this conjecture when (G ₁) = 3, for sufficiently large n.* This work was supported in part by a grant from National Science Foundation (DMS-9801396). Partially supported by OTKA T034475. Part of this work was done while the authors were graduate students at Rutgers University; Research partially supported by a DIMACS fellowship.     

Global cycle properties in graphs with large minimum clustering coefficient

Let 𝒫 be a graph property. A graph G is said to be locally 𝒫 (closed locally 𝒫) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property 𝒫. The clustering coefficient of a vertex is the proportion of pairs of its neighbours that are themselves neighbours. The minimum clustering coefficient of G is the smallest clustering coefficient among all vertices of G. Let H be a subgraph of a graph G and let S ? V (H). We say that H is a strongly induced subgraph of G with attachment set S, if H is an induced subgraph of G and the vertices of V (H) ? S are not incident with edges that are not in H. A graph G is fully cycle extendable if every vertex of G lies in a triangle and for every nonhamiltonian cycle C of G, there is a cycle of length |V (C)|?+?1 that contains the vertices of C. A complete characterization, of those locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 that are fully cycle extendable, is given in terms of forbidden strongly induced subgraphs (with specified attachment sets). Moreover, it is shown that all locally connected graphs with Δ?≤?6 and sufficiently large minimum clustering coefficient are weakly pancylic, thereby proving Ryj´ǎcek’s conjecture for this class of graphs.     

Bounding the diameter of distance-regular graphs

LetG be a connected distance-regular graph with valencyk>2 and diameterd, but not a complete multipartite graph. Suppose that is an eigenvalue ofG with multiplicitym and that±k. We prove that bothd andk are bounded by functions ofm. This implies that, ifm>1 is given, there are only finitely many connected, co-connected distance-regular graphs with an eigenvalue of multiplicitym.This work was supported by NSERC grant A5367.     

Covering simply connected regions by rectangles

We prove that the ratio of the minimum number of rectangles covering a simply connected board (polyomino)B and the maximum number of points inB no two of which are contained in a common rectangle is less than 2. This research was partially supported by MEV (Budapest).     

On a class of isometric subgraphs of a graph

In a graphG, which has a loop at every vertex, a connected subgraphH=(V(H),E(H)) is a retract if, for anya, b ∈V(H) and for any pathsP, Q inG, both joininga tob, and satisfying |Q|≧ ≧|P|, thenP ⫅V(H) wheneverQ ⫅V(H). As such subgraphs can be described by a closure operator we are led to the investigation of the corresponding complete lattice of “closed” subgraphs. For example, in this complete lattice every element is the infimum of an irredundant family of infimum irreducible elements. The work presented here was supported in part by N.S.E.R.C. Operating Grant No. A4077.     

Decomposing Berge Graphs Containing No Proper Wheel, Long Prism Or Their Complements

In this paper we show that, if G is a Berge graph such that neither G nor its complement contains certain induced subgraphs, named proper wheels and long prisms, then either G is a basic perfect graph( a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that G is perfect. This work was supported in part by NSF grant DMI-0352885 and ONR grant N00014-03-1-0188.     

On packing bipartite graphs

G andH, two simple graphs, can be packed ifG is isomorphic to a subgraph of , the complement ofH. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees ofG andH. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.the paper was written while the authors were graduate students at the University of Chicago and was completed while the first author was at M.I.T. The work of the first author was supported in part by the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. The work of the second author was supported in part by NSF grant CCR-8706518.     

An algorithm for packing non-zero A-paths in group-labelled graphs

Let G = (V, E) be an oriented graph whose edges are labelled by the elements of a group Γ and let A ⊆ V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Γ is not abelian, we sum the labels in their order along the path.) We give an efficient algorithm for finding a maximum collection of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. This research was partially conducted during the period Chudnovsky served as a Clay Mathematics Institute Long-Term Prize Fellow. The research was supported in part by the Natural Sciences and Engineering Council of Canada.     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

Graph properties for splitting with grounded Laplacian matrices

With any undirected, connected graphG containing no self-loops one can associate the Laplacian matrixL(G). It is also the (singular) admittance matrix of a resistive network with all conductances taken to be unity. While solving the linear system involved, one of the vertices is grounded, so the coefficient matrix is a principal submatrix ofL which we will call the grounded Laplacian matrixL ₁. In this paper we consider iterative solutions of such linear systems using certain regular splittings ofL ₁ and derive an upper bound for the spectral radius of the iteration matrix in terms of the properties of the graphG.This work was supported by the Academy of Finland     

Decomposition of 3-connected graphs

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K _3,n for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.