Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

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.     

The integrity of a cubic graph

Integrity, a measure of network reliability, is defined as

where G is a graph with vertex set V and m(G−S) denotes the order of the largest component of G−S. We prove an upper bound of the following form on the integrity of any cubic graph with n vertices:

Moreover, there exist an infinite family of connected cubic graphs whose integrity satisfies a linear lower bound I(G)>βn for some constant β. We provide a value for β, but it is likely not best possible. To prove the upper bound we first solve the following extremal problem. What is the least number of vertices in a cubic graph whose removal results in an acyclic graph? The solution (with a few minor exceptions) is that n/3 vertices suffice and this is best possible.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

On the planarity of jump graphs

For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph J_k(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of J_k(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J₂(G) is planar are determined.     

Eulerian subgraphs containing given edges

For an integer l0, define to be the family of graphs such that if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in . Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in [J. Graph Theory 1 (1977) 79–84] and [J. Graph Theory 3 (1979) 91–93] are extended.     

Reconstruction of infinite locally finite connected graphs

Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set . We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ω_i)_0i (n2) of pairwise finitely separable subsets of such that, for all x,y,x′,y′V(G) and every isomorphism f of G−{x,y} onto G−{x′,y′} there is a permutation π of {0,…,n−1} such that for 0i<n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

Harary's conjectures on integral sum graphs

Let N denote the set of positive integers and Z denote all integers. The (integral) sum graph of a finite subset S N(Z) is the graph (S, E) with uv ε E if and only if u + v ε S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S N(Z). The (integral) sum number of a given graph G is the smallest number of isolated nodes which when added to G result in an (integral) sum graph.

We show that the integral sum number of a complete graph with n 4 nodes equals 2n − 3, which proves a conjecture of Harary. And we disprove another conjecture of Harary by showing that there are infinitely many trees which are not caterpillars but are integral sum graphs.     

The connectivity of a graph on uniform points on [0,1]

A random graph G_n(x) is constructed on independent random points U₁,…,U_n distributed uniformly on [0,1]^d, d1, in which two distinct such points are joined by an edge if the l_∞-distance between them is at most some prescribed value 0<x<1. The connectivity distance c_n, the smallest x for which G_n(x) is connected, is shown to satisfy

(1)

For d2, the random graph G_n(x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: c_n/d_n→1, a.s., as n→∞, where d_n is the largest nearest-neighbor link, the smallest x for which G_n(x) has no isolated vertices.     

The coordinate representation of a graph and n-universal graph of radius 1

Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space Eⁿ. Cube vertices have integer coordinates. The coordinate matrix, A(G)={v_nk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements v_nk≠v_pk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3ⁿ⁻² vertices that contains as an induced subgraph a copy of any graph on n vertices.     

On the minor-minimal 2-connected graphs having a fixed minor

Let H be a graph with κ₁ components and κ₂ blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ₁−1)+β(κ₂−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.     

Complexity of projected images of convex subdivisions

Let S be a subdivision of ^d into n convex regions. We consider the combinatorial complexity of the image of the (k - 1)-skeleton of S orthogonally projected into a k-dimensional subspace. We give an upper bound of the complexity of the projected image by reducing it to the complexity of an arrangement of polytopes. If k = d − 1, we construct a subdivision whose projected image has Ω(n^(3d−2)/2) complexity, which is tight when d 4. We also investigate the number of topological changes of the projected image when a three-dimensional subdivision is rotated about a line parallel to the projection plane.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.     

Multiplicative properties of generalized matrix functions

We consider scalar-valued matrix functions for n×n matrices A=(a_ij) defined by Where G is a subgroup of S_n the group of permutations on n letters, and χ is a linear character of G. Two such functions are the permanent and the determinant. A function (1) is multiplicative on a semigroup S of n×n matrices if d(AB)=d(A)d(B) AB∈S.

With mild restrictions on the underlying scalar ring we show that every element of a semigroup containing the diagonal matrices on which (1) is multiplicative can have at most one nonzero diagonal(i.e., diagonal with all nonzero entries)and conversely, provided that χ is the principal character(χ≡1).     

Degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle

Let 1a<b be integers and G a Hamiltonian graph of order |G|(a+b)(2a+b)/b. Suppose that δ(G)a+2 and max{deg_G(x), deg_G(y)}a|G|/(a+b)+2 for each pair of nonadjacent vertices x and y in G. Then G has an [a,b]-factor which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. For the case of odd a=b, there exists a graph satisfying the conditions of the theorem but having no desired factor. As consequences, we have the degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle.     

Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G'sbipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d(K_n) = [log₂n], η(K_n) = d(K_n) for n 16, and η(K_n) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.     

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.