Longest cycles in k-connected graphs with given independence number

The Chvátal–Erd?s Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In 1976, Fouquet and Jolivet conjectured an extension: If G is an n-vertex k-connected graph with independence number a, and a?k, then G has a cycle with length at least . We prove this conjecture.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

The number of edges in a bipartite graph of given radius

Vizing established an upper bound on the size of a graph of given order and radius. We find a sharp upper bound on the size of a bipartite graph of given order and radius.     

On the number of edges in the transitive closure of a graph

A property of the square sum of partitions of integers is investigated. The square sum has a direct relation to the number of edges in the transitive closure of a graph. This paper is concerned with the problem of determining the minimum missing value in the sequence of square sums. Asymptotically tight lower and upper bounds on this value are obtained. A consequence of the main result for closure size prediction is also mentioned.     

The maximum number of edges in a minimal graph of diameter 2

A graph g of diameter 2 is minimal if the deletion of any edge increases its diameter. Here the following conjecture of Murty and Simon is proved for n < n_o. If g has n vertices then it has at most n²/4 edges. The only extremum is the complete bipartite graph.     

The minimum number of triangles covering the edges of a graph

Suppose that a connected graph G has n vertices and m edges, and each edge is contained in some triangle of G. Bounds are established here on the minimum number t_min(G) of triangles that cover the edges of G. We prove that ?(n - 1)/2? ? t_min(G) with equality attained only by 3-cactii and by strongly related graphs. We obtain sharp upper bounds: if G is not a 4-clique, then. The triangle cover number t_min(G) is also bounded above by Γ(G) = m - n + c, the cyclomatic number of a graph G of order n with m edges and c connected components. Here we give a combinatorial proof for t_min(G) ? Γ(G) and characterize the family of all extremal graphs satisfying equality.     

Bounds for the number of meeting edges in graph partitioning

Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w ₁?Δ₁)/2+2w ₂/3, where wi is the total weight of edges of size i and Δ₁ is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w ₀?1)/6+(w ₁?Δ₁)/3+2w ₂/3, where w ₀ is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K ₂ and K _1,3, admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobás and Scott.     

Diameter-vital edges in a graph

The graph resulting from contracting edge e is denoted as G/e and the graph resulting from deleting edge e is denoted as G − e. An edge e is diameter-essential if diam(G/e) < diam(G), diameter-increasing if diam(G − e) < diam(G), and diameter-vital if it is both diameter-essential and diameter-increasing. We partition the edges that are not diameter-vital into three categories. In this paper, we study realizability questions relating to the number of edges that are not diameter-vital in the three defined categories. A graph is diameter-vital if all its edges are diameter-vital. We give a structural characterization of diameter-vital graphs.     

On the number of edges in induced subgraphs of a special distance graph

We obtain new estimates for the number of edges in induced subgraphs of a special distance graph.     

Diameter-essential edges in a graph

The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity among the vertices of G. The contraction of edge e=uv in G consists of removing e and identifying u and v as a single new vertex w, where w is adjacent to any vertex that at least one of u or v were adjacent to. The graph resulting from contracting edge e is denoted G/e. An edge e is diameter-essential if diam(G/e)<diam(G). Let c(G) denote the number of diameter-essential edges in graph G. In this paper, we study existence and extremal problems for c(G); determine bounds on c(G) in terms of diameter and order; and obtain characterizations of graphs achieving extreme values of c(G).     

Covering vertices of a graph by k disjoint cycles

Let d, k and n be three integers with k3, d4k−1 and n3k. We show that if d(x)+d(y)d for each pair of nonadjacent vertices x and y of a graph G of order n, then G contains k vertex-disjoint cycles converting at least min{d,n} vertices of G.     

On the number of vertices and edges of the Buneman graph

In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splitsS, the vertices of the Buneman graph correspond precisely to the subsetsS′ ofS such that the splits inS′ are pairwise incompatible and the edges correspond to pairs (S′, S) withS′ as above andS∈S′. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits inS are compatible.     

Partitioning the edges of a graph

For any integer m (≥2), it is known that there are simple graphs of maximum valence m whose edges cannot be coloured with m colours in such a way that adjacent edges shall have different colours. We find those values of m and k for which it is true that every simple graph whose maximum valence does not exceed mk can be coloured with m colours in such a way that no colour appears more than k times at any vertex.     

Edges not contained in triangles and the number of contractible edges in a 4-connected graph

Let G be a 4-connected graph, and let E_c(G) denote the set of 4-contractible edges of G and let denote the set of those edges of G which are not contained in a triangle. Under this notation, we show that if , then we have .     

An upper bound on the paired-domination number in terms of the number of edges in the graph

In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by , is the minimum cardinality of a paired-dominating set in G. We show that if G is a connected graph of size m≥18 with minimum degree at least 2, then and we characterize the (infinite family of) graphs that achieve equality in this bound.