Subgraph distances in graphs defined by edge transfers

For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E(F), wx ε E(G) - E(F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J(G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{J^k(G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence.     

ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M₆ and M₇.     

Complete-factors and f-factors

A factor F of a graph is called a complete-factor if each component of F is complete. Let G be a graph, F be a complete-factor of G with ω(F)2, and f be an integer-valued function defined on V(G) with ∑_xV(G)f(x) even. If G−V(C) has an f-factor for each component C of F, then G has an f-factor.     

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.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

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.     

Minimal configuration trees

A graph is singular of nullity η if zero is an eigenvalue of its adjacency matrix with multiplicity η. If η(G)=1, then the core of G is the subgraph induced by the vertices associated with the non-zero entries of the zero-eigenvector. A connected subgraph of G with the least number of vertices and edges, that has nullity one and the same core as G, is called a minimal configuration. A subdivision of a graph G is obtained by inserting a vertex on every edge of G. We review various properties of minimal configurations. In particular, we show that a minimal configuration is a tree if and only if it is a subdivision of some other tree.     

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.     

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.     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

Connectivity of generalized prisms over G

The problem of building larger graphs with a given graph as an induced subgraph is one which can arise in various applications and in particular can be important when constructing large communications networks from smaller ones. What one can conclude from this paper is that generalized prisms over G may provide an important such construction because the connectivity of the newly created graph is larger than that of the original (connected) graph, regardless of the permutation used.

For a graph G with vertices labeled 1,2,…, n and a permutation in S_n, the generalized prisms over G, (G) (also called a permutation graph), consists of two copies of G, say G_x and G_y, along with the edges (x_i, y_(i), for 1≤i≤n. The purpose of this paper is to examine the connectivity of generalized prisms over G. In particular, upper and lower bounds are found. Also, the connectivity and edge-connectivity are determined for generalized prisms over trees, cycles, wheels, n-cubes, complete graphs, and complete bipartite graphs. Finally, the connectivity of the generalized prism over G, (G), is determined for all in the automorphism group of G.     

Measurements of edge-uncolorability

Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let c_k be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r₃=|E|−c₃ and . We show that on one side r₃ and r₂ bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r₃ and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr₃. For k=2,3, let ζ_k denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other.     

Remarks on the bondage number of planar graphs

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

On index of total boundedness of (strictly) o-bounded groups

Let G be a metrizable topological group. Denote by itb(G) the smallest cardinality of a cover of G by totally bounded subsets of G. A group G is defined to be σ-bounded if itb(G)₀. The group G is called o-bounded if for every sequence (U_n)_nω of neighborhoods of the identity in G there exists a sequence (F_n)_nω of finite subsets in G such that G=_nωF_n·U_n; G is called strictly o-bounded (respectively OF-determined) if the second player (respectively one of the players) has a winning strategy in the following game OF: two players, I and II, choose at every step n an open neighborhood U_n of the identity in G and a finite subset F_n of G, respectively. The player II wins if G=_nωF_n·U_n.

For a second countable group G the following results are proven. . If G is strictly o-bounded, then itb(G)₁ and G is σ-bounded or meager. If the space G is analytic, then the group is OF-determined and satisfies . G is σ-bounded if it is strictly o-bounded and one of the following conditions holds: (i) G is analytic; (ii) ; (iii) (MA+¬CH) holds; (iv) analytic games are determined; (v) there exists a measurable cardinal. Also we show that under (MA) every non-locally compact Polish Abelian divisible group contains a Baire o-bounded OF-undetermined subgroup.     

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.     

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.     

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.     

Graphs whose acyclic graphoidal covering number is one less than its maximum degree

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. In this paper we characterize the class of graphs G for which η_a=Δ−1 where Δ is the maximum degree of a vertex in G.     

Existence results for doubly near resolvable (υ, 3, 2)-BIBDs

Let V be a set of υ elements. A (1, 2; 3, υ, 1)-frame F is a square array of side v which satisfies the following properties. We index the rows and columns of F with the elements of V, V={x₁,x₂,…,x_υ}. (1) Each cell is either empty or contains a 3-subset of V. (2) Cell (x_i, x_i) is empty for i=1, 2,…, υ. (3) Row x_i of F contains each element of V−{x_i} once and column x_i of F contains each element of V−{x_i} once. (4) The collection of blocks obtained from the nonempty cells of F is a (υ, 3, 2)-BIBD. A (1, 2; 3, υ, 1)-frame is a doubly near resolvable (υ, 3, 2)-BIBD. In this paper, we first present a survey of existence results on doubly near resolvable (υ, 3, 2)-BIBDs and (1, 2; 3, υ, 1)-frames. We then use frame constructions to provide a new infinite class of doubly near resolvable (υ, 3, 2)-BIBDs by constructing (1, 2; 3, υ, 1)-frames.