Bounds for the covering number of a graph

Upper and lower bounds for the covering number of a graph are obtained. It is shown, by probabilistic methods, that there exists a large class of graphs for which the upper bound obtained is essentially best possible.     

Further remarks on partitioning the edges of a graph

The main result is that if m and k are odd integers with m ≥ k ≥ 1, then any graph which is the union of m graphs of maximum valence k is also the union of k graphs of maximum valence m. This is not generally true if k > m.     

Bounds for the harmonious chromatic number of a graph

The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (Journal of Graph Theory, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (Journal of Graph Theory, 1989, pp. 291–298) are improved.     

Bounds for the ramsey number of a disconnected graph versus any graph

Bounds are determined for the Ramsey number of the union of graphs versus a fixed graph H, based on the Ramsey number of the components versus H. For certain unions of graphs, the exact Ramsey number is determined. From these formulas, some new Ramsey numbers are indicated. In particular, if . Where k_i is the number of components of order i and t₁ (H) is the minimum order of a color class over all critical colorings of the vertices of H, then .     

Bounds on the connected domination number of a graph

A subset S$S$ of vertices in a graph G=(V,E)$G=(V,E)$ is a connected dominating set of G$G$ if every vertex of V?S$V?S$ is adjacent to a vertex in S$S$ and the subgraph induced by S$S$ is connected. The minimum cardinality of a connected dominating set of G$G$ is the connected domination number _γc(G)${\gamma }_c\left(G\right)$. The girth g(G)$g\left(G\right)$ is the length of a shortest cycle in G$G$. We show that if G$G$ is a connected graph that contains at least one cycle, then _γc(G)≥g(G)−2${\gamma }_c\left(G\right)\ge g\left(G\right)-2$, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results.     

Bounds on the number of isolates in sum graph labeling

A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L(w)=L(u)+L(v). The sum number σ(G) of a graph G=(V,E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that σ(G)|E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G=(V,E) with fixed |V|3 and |E|, the average of σ(G) is at least

Full-size image

. In other words, for most graphs, σ(G)Ω(|E|).     

On the average crosscap number Ⅱ: Bounds for a graph

The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less than 2β(G)-1/2β(G)-1β(G)β(G) and not larger than/β(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.     

On the average crosscap number II: Bounds for a graph

The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less thanβ(G)-1/2β(G)-1β(G) and not larger thanβ(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.     

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.     

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.     

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.     

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.     

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.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal 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.     

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.     

Bounds on the number of cycles of length three in a planar graph

LetG be ap-vertex planar graph having a representation in the plane with nontriangular facesF ₁,F ₂, …,F _r. Letf ₁,f ₂, …,f _r denote the lengths of the cycles bounding the facesF ₁,F ₂, …,F _r respectively. LetC ₃(G) be the number of cycles of length three inG. We give bounds onC ₃(G) in terms ofp,f ₁,f ₂, …,f _r. WhenG is 3-connected these bounds are bounds for the number of triangles in a polyhedron. We also show that all possible values ofC ₃(G) between the maximum and minimum value are actually achieved. This research was supported in part by the U.S.A.F. Office of Scientific Research, Systems Command, under Grant AFOSR-76-3017 and the National Science Foundation under Grant ENG79-09724.