Networks with small stretch number

In a previous work, the authors introduced the class of graphs with bounded induced distance of order k (BID(k) for short), to model non-reliable interconnection networks. A network modeled as a graph in BID(k) can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is at most k times the distance in the non-faulty graph. The smallest k such that GBID(k) is called stretch number of G. We show an odd characteristic of the stretch numbers: every rational number greater or equal 2 is a stretch number, but only discrete values are admissible for smaller stretch numbers. Moreover, we give a new characterization of classes BID(2−1/i), i1, based on forbidden induced subgraphs. By using this characterization, we provide a polynomial time recognition algorithm for graphs belonging to these classes, while the general recognition problem is Co-NP-complete.     

图的区间边着色的收缩图方法

图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类.     

A generalisation of the diameter of a graph

We prove the following theorem. If G is a connected finite graph of order p, and S is a k-subset of V(G) (where k≥2), then there is a pair of vertices in S which are at a distance ≤2(p−1)/k if k does not divide p, and ≤2(p−1)/k + 1 otherwise.     

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.     

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c：E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ'_(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。在图G中,如果mad(G) < 3并且Δ≤4,那么χ'_(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ'_(1,0)(G)≤3Δ-1。     

Pancyclicity mod k of claw-free graphs and K1,4-free graphs

For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K_1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs.     

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.     

On the Differential Polynomial of a Graph

We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G; x) :=∑?(G)k=-nB_k(G) x~(n+k), where B_k(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G;x) and its coefficients.In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G.     

Primitive graphs with given exponents and minimum number of edges

A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even.     

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.     

Matching extension and minimum degree

Let G be a simple connected graph on 2n vertices with a perfect matching. For a given positive integer k, 1 k n − 1, G is k-extendable if for every matching M of size k in G, there exists a perfect matching in G containing all the edges of M. The problem that arises is that of characterizing k-extendable graphs. In this paper, we establish a necessary condition, in terms of minimum degree, for k-extendable graphs. Further, we determine the set of realizable values for minimum degree of k-extendable graphs. In addition, we establish some results on bipartite graphs including a sufficient condition for a bipartite graph to be k-extendable.     

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.     

Holes in random graphs

It is shown that for every >0 with the probability tending to 1 as n→∞ a random graph G(n,p) contains induced cycles of all lengths k, 3 ≤ k ≤ (1 − )n log c/c, provided c(n) = (n − 1)p(n)→∞.     

Graph spectra

The k-spectrum s_k(G) of a graph G is the set of all positive integers that occur as the size of an induced k-vertex subgraph of G. In this paper we determine the minimum order and size of a graph G with s_k (G) = {0, 1, …,(₂^k)} and consider the more general question of describing those sets S {0,1, … ,(₂^k)} such that S = s_k(G) for some graph G.     

An Extension of an Inequality Involving Symmetric Products with an Application to Permanents

Let A be an nk × nk positive semi-definite symmetric matrix partitioned into blocks A^ij each of which is an n × n matrix. In [2] Mine states a conjecture of Marcus that per(A) ≥ per(G) where G is the k × k matrix [per(A^ij)]. In this paper we prove a weaker inequality namely that per(A) ≥ (k!)^-1per(G).     

Polynomially solvable cases for the maximum stable set problem

We describe two classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedure which, at each step, builds from a graph G a new graph G′ which has fewer vertices and has the property that (G′) = (G) − 1. For the second class, it can be decided in polynomial time whether there exists a stable set of given size k.     

The Best Lower Bound for the Permanent of a Correlation Matrix of Rank Two

If 1≤k≤n, then Cor(n,k) denotes the set of all n×n real correlation matrices of rank not exceeding k. Grone and Pierce have shown that if A∈Cor (n, n-1), then per(A)≥n/(n-1). We show that if A∈Cor(n,2), then , and that this inequality is the best possible.     

Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.     

On approximation intractability of the path–distance–width problem

Path–distance–width of a graph G=(V,E), denoted by pdw(G), is the minimum integer k satisfying that there is a nonempty subset of SV such that the number of the nodes with distance i from S is at most k for any nonnegative integer i. It is known that given a positive integer k and a graph G, the decision problem pdw(G)k is NP-complete even if G is a tree (Yamazaki et al. Lecture Notes in Computer Science, vol. 1203, Springer, Berlin, 1997, pp. 276–287). In this paper, we show that it is NP-hard to approximate the path–distance–width of a graph within a ratio for any >0, even for trees.     

Cyclic coloring of plane graphs

Let G be a plane graph, and let χ_k(G) be the minimum number of colors to color the vertices of G so that every two of them which lie in the boundary of the same face of the size at most k, receive different colors. In 1966, Ore and Plummer proved that χ_k(G)2k for any k3. It is also known that χ₃(G)4 (Appel and Haken, 1976) and χ₄(G)6 (Borodin, 1984). The result in the present paper is: χ₅(G)9, χ₆(G)11, χ₇(G)12, and χ_k(G)2k − 3 if k8.