A generalization of menger's theorem for certain block—cactus graphs

A graphG is called a block—cactus graph if each block ofG is complete or a cycle. In this paper, we shall show that a block—cactus graphG has the property that the cardinality of a smallest set separating any vertex setJ ofG is the maximum number of internally disjoint paths between the vertices ofJ if and only if every block ofG contains at most two cut-vertices. This result extends two theorems of Sampathkumar [4] and [5].     

Special subdivisions ofK 4 and 4-chromatic graphs

In this paper we consider special subdivisions ofK ₄ in which some of the edges are left undivided. A best possible extremal-result for the case where the edges of a Hamiltonian path are left undivided is obtained. Moreover special subdivisions as subgraphs of 4-chromatic graphs are studied. Our main-result on 4-chromatic graphs says that any 4-critical graphG contains an odd cycleC without diagonals such thatG-V (C) is connected.     

On the power of a perturbation for testing non-isomorphism of graphs

In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.This work was supported by the U.S. Army Research Office under Grant DAAG29-82-K-0107.     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

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.)     

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 thel-connectivity of a graph

For an integerl 2, thel-connectivity of a graphG is the minimum number of vertices whose removal fromG produces a disconnected graph with at leastl components or a graph with fewer thanl vertices. A graphG is (n, l)-connected if itsl-connectivity is at leastn. Several sufficient conditions for a graph to be (n, l)-connected are established. IfS is a set ofl( 3) vertices of a graphG, then anS-path ofG is a path between distinct vertices ofS that contains no other vertices ofS. TwoS-paths are said to be internally disjoint if they have no vertices in common, except possibly end-vertices. For a given setS ofl 2 vertices of a graphG, a sufficient condition forG to contain at leastn internally disjointS-paths, each of length at most 2, is established.     

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     

Families of cuts with the MFMC-property

A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class has the MFMC-property if and only if it is one of (i), (ii), (iii).     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

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.     

Cycles of relatively prime length and the road coloring problem

We give a partial answer to theroad coloring problem, a purely graphtheoretical question with applications in both symbolic dynamics and automata theory. The question is whether for any positive integerk and for any aperiodic and strongly connected graphG with all vertices of out-degreek, we can labelG with symbols in an alphabet ofk letters so that all the edges going out from a vertex take a different label and all paths inG presenting a wordW terminate at the same vertex, for someW. Such a labelling is calledsynchronizing coloring ofG. Anyaperiodic graphG contains a setS of cycles where the greatest common divisor of the lengths equals 1. We establish some geometrical conditions onS to ensure the existence of a synchronizing coloring.     

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.     

A property of weighted graphs without induced cycles of nonpositive weights

It has been conjectured [B. Xu, On signed cycle domination in graphs, Discrete Math. 309 (4) (2009) 1007–1012] that if there is a mapping from the edge set of a 2-connected graph G to {−1,1} such that for each induced subgraph, that is a cycle, the sum of all numbers assigned to its edges by this mapping is positive, then the number of all those edges of G to which 1 is assigned, is more than the number of all other edges of G. This conjecture follows from the main result of this note: If a mapping assigns integers as weights to the edges of a 2-connected graphGsuch that for each edge, its weight is not more than 1 and for each cycle which is an induced subgraph ofG, the sum of all weights of its edges is positive, then the sum of all weights of the edges ofGalso is positive. A simple corollary of this result is the following: If?is a mapping from the edge set of a 2-connected graphGto a set of real numbers such that for each cycleCofG, ∑_e∈E(C)?(e)>0, then∑_e∈E(G)?(e)also is positive.     

Matching-perfect and cover-perfect graphs

It is shown that a graphG has all matchings of equal size if and only if for every matching setλ inG, G\V(λ) does not contain a maximal open path of odd length greater than one, which is not contained in a cycle. (V(λ) denotes the set of vertices incident with some edge ofλ.) Subsequently edge-coverings of graphs are discussed. A characterization is supplied for graphs all whose minimal covers have equal size.     

On the<Emphasis Type="Italic">k</Emphasis>-systems of a simple polytope

Ak-system of the graphG _P of a simple polytopeP is a set of induced subgraphs ofG _P that shares certain properties with the set of subgraphs induced by thek-faces ofP. This new concept leads to polynomial-size certificates in terms ofG _P for both the set of vertex sets of facets and for abstract objective functions (AOF) in the sense of Kalai. Moreover, it is proved that an acyclic orientation yields an AOF if and only if it induces a unique sink on every 2-face.     

The perfectly Matchable Subgraph Polytope of an arbitrary graph

The Perfectly Matchable Subgraph Polytope of a graphG=(V, E), denoted byPMS(G), is the convex hull of the incidence vectors of thoseXV which induce a subgraph having a perfect matching. We describe a linear system whose solution set isPMS(G), for a general (nonbipartite) graphG. We show how it can be derived via a projection technique from Edmonds' characterization of the matching polytope ofG. We also show that this system can be deduced from the earlier bipartite case [2], by using the Edmonds-Gallai structure theorem. Finally, we characterize which inequalities are facet inducing forPMS(G), and hence essential.     

Panarboreal graphs

An ordinary graphG will be calledpanarboreal if it contains all possible trees, i.e. if, for every treeT with |V(T)|=|V(G)|,G has a subgraph which is isomorphic toT. We derive sufficient conditions for a graphG to be panarboreal in terms of Δ(G) and δ(G).     

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.     

On barrier sets of star-factors

A barrier set of a graphG for a star-factor is a setS ofV(G) such thati(G – S) > k|S|, wherei(G – S) denotes the number of isolated vertices ofG – S. In this paper, we obtain some results on barrier sets.