Heavy cycles in k-connected weighted graphs with large weighted degree sums

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. The weight of a cycle is defined as the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with it. In this paper, we prove that: Let G be a k-connected weighted graph with k?2. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/(k+1), if G satisfies the following conditions: (1) The weighted degree sum of any k+1 pairwise nonadjacent vertices is at least m; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This generalizes an early result of Enomoto et al. on the existence of heavy cycles in k-connected weighted graphs.     

Edge coloring of hypergraphs and a conjecture of ErdÖs,Faber, Lovász

Call a bypergraphsimple if for any pairu, v of distinct vertices, there is at most one edge incident to bothu andv, and there are no edges incident to exactly one vertex. A conjecture of Erds, Faber and Lovász is equivalent to the statement that the edges of any simple hypergraph onn vertices can be colored with at mostn colors. We present a simple proof that the edges of a simple hypergraph onn vertices can be colored with at most [1.5n-2 colors].This research was partially supported by N.S.F. grant No. MCS-8311422.     

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.* This work was supported in part by NSF grant CCR-9700239 and by DIMACS. This work was done while a postdoctoral fellow at DIMACS.     

Planar graphs and poset dimension

We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<_G b if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <_G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.     

Equitable Coloring of Three Classes of 1-planar Graphs

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree Δ at least 15, 13 or 12 has an equitable Δ-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.     

Changing and unchanging domination: a classification

The six classes of graphs resulting from the changing or unchanging of the domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. Each of these classes has been studied individually in the literature. We consider relationships among the classes, which are illustrated in a Venn diagram. We show that no subset of the Venn diagram is empty for arbitrary graphs, and prove that some of the subsets are empty for connected graphs. Our main result is a characterization of trees in each subset of the Venn diagram.     

Symmetric Graphs and Flag Graphs

 With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them. In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B. The work was supported by a discovery-project grant from the Australian Research Council. Received April 24, 2001; in revised form October 9, 2002 Published online May 9, 2003     

Cycles through ten vertices in 3-connected cubic graphs

It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore, we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under which it has a cycle through four chosen vertices and two edges. We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices each map to a distinct vertex of the Petersen graph.     

Color degree and monochromatic degree conditions for short properly colored cycles in edge‐colored graphs

For an edge‐colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge‐colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge‐colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge‐colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.     

Density Conditions for Panchromatic Colourings of Hypergraphs

Let be a hypergraph. A panchromatic t-colouring of is a t-colouring of its vertices such that each edge has at least one vertex of each colour; and is panchromatically t-choosable if, whenever each vertex is given a list of t colours, the vertices can be coloured from their lists in such a way that each edge receives at least t different colours. The Hall ratio of is . Among other results, it is proved here that if every edge has at least t vertices and whenever , then is panchromatically t-choosable, and this condition is sharp; the minimum such that every t-uniform hypergraph with is panchromatically t-choosable satisfies ; and except possibly when t = 3 or 5, a t-uniform hypergraph is panchromatically t-colourable if whenever , and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equal its maximum degree. Received November 10, 1998 RID="*" ID="*" This work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.     

Density Conditions For Triangles In Multipartite Graphs

We consider the problem of finding a large or dense triangle-free subgraph in a given graph G. In response to a question of P. Erdős, we prove that, if the minimum degree of G is at least 9|V (G)|/10, the largest triangle-free subgraphs are precisely the largest bipartite subgraphs in G. We investigate in particular the case where G is a complete multipartite graph. We prove that a finite tripartite graph with all edge densities greater than the golden ratio has a triangle and that this bound is best possible. Also we show that an infinite-partite graph with finite parts has a triangle, provided that the edge density between any two parts is greater than 1/2.     

Directed cut transversal packing for source-sink connected graphs

Concerning the conjecture that in every directed graph, a maximum packing of directed cut transversals is equal in cardinality to a minimum directed cut, a proof is given for the side coboundaries of a graph. This case includes, and is essentially equivalent to, all source-sink connected graphs, for which Schrijver has given a proof. The method used here first reduces the assertion to a packing theorem for bi-transversals. A packing of bi-transversals of the required size is constructed one edge at a time, by maintaining a Hall-like feasibility condition as each edge is added.     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

Hypergraph Extension Of The Alon-Tarsi List Coloring Theorem

A circulation in a digraph is a spanning subgraph with indegree equal to outdegree at each vertex. Alon and Tarsi proved that a graph is d-choosable when it has an orientation that has no vertex of outdegree at least d and has the property that the numbers of circulations with even-sized and odd-sized edge sets differ. We generalize this to k-uniform hypergraphs for prime k. We use a hypergraph polynomial and a notion of hypergraph orientation defined by choosing a source vertex from each edge.* Project sponsored by the National Security Agency under Grant Number MDA904-03-1-0037. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.     

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 are interested in the maximum number of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. The general case also includes Mader's S-paths problem. We prove that for any positive integer k, either there are k vertex-disjoint A-paths each of non-zero weight, or there is a set of at most 2k −2 vertices that meets each of the non-zero A-paths. This result is obtained as a consequence of an exact min-max theorem. These results were obtained at a workshop on Structural Graph Theory at the PIMS Institute in Vancouver, Canada. This research was partially conducted during the period the first author served as a Clay Mathematics Institute Long-Term Prize Fellow.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

On the connectivity of randomm-orientable graphs and digraphs

We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex. We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences. We also examine the relationship between our results and certain results of Erdős and Rényi.     

Some properties of graphs determined by edge zeta functions

In 1989, Hashimoto introduced an edge zeta function of a finite graph, which is a generalization of the Ihara zeta function. The edge zeta function is the reciprocal of a polynomial in twice as many indeterminants as edges in the graph and can be computed via a determinant expression. We look at graph properties which we can determine using the edge zeta function. In particular, the edge zeta function is enough to deduce the clique number, the number of Hamiltonian cycles, and whether a graph is perfect or chordal. Finally, we present a new example illustrating that the Ihara zeta function cannot necessarily do the same.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

The asymptotic number of graphs not containing a fixed color-critical subgraph

For a finite graphG letForb(H) denote the class of all finite graphs which do not containH as a (weak) subgraph. In this paper we characterize the class of those graphsH which have the property that almost all graphs inForb(H) are -colorable. We show that this class corresponds exactly to the class of graphs whose extremal graph is the Turán-graphT _n ().An earlier result of Simonovits (Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions,Discrete Math. 7 (1974), 349–376) shows that these are exactly the (+1)-chromatic graphs which contain a color-critical edge.