Note on the connectivity of line graphs

Let G be a connected graph with vertex set V(G), edge set E(G), vertex-connectivity κ(G) and edge-connectivity λ(G).A subset S of E(G) is called a restricted edge-cut if G−S is disconnected and each component contains at least two vertices. The restricted edge-connectivity λ₂(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ₂(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that

     

Super restricted edge connected Cartesian product graphs

An edge-cut F of a connected graph G is called a restricted edge-cut if G−F contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity λ^′(G) of G. A graph G is said to be λ^′-optimal if λ^′(G)=ξ(G), where ξ(G) is the minimum edge-degree of G. A graph is said to be super-λ^′ if every minimum restricted edge-cut isolates an edge. This article gives a sufficient condition for Cartesian product graphs to be super-λ^′. Using this result, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to be super-λ^′.     

Super connectivity of line graphs

The super connectivity κ^′ and the super edge-connectivity λ^′ are more refined network reliability indices than connectivity κ and edge-connectivity λ. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ^′(L(G))=λ^′(G) if and only if G is not super-λ^′. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G))=λ^′(G). Furthermore, the authors show that the line graph of a super-λ^′ graph is super-λ if the minimum degree is at least three.     

A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ²(AG₄)=4 and κ²(AGn)=6n−18 for n?5.     

Arc fault tolerance of cartesian product digraphs on hyper arc connectivity

A strongly connected digraph D is hyper-λ if the removal of any minimum arc cut of D results in exactly two strong components, one of which is a singleton. We define a hyper-λ digraph D to be m-hyper-λ if D?S is still hyper-λ for any arc set S with ∣S∣≤m. The maximum integer of such m, denoted by H_λ(D), is said to be the arc fault tolerance of D on the hyper-λ property. H_λ(D) is an index to measure the reliability of networks. In this paper, we study H_λ(D) for the cartesian product digraph D=D₁×D₂. We give a necessary and sufficient condition for D₁×D₂ to be hyper-λ and give the lower and upper bounds on H_λ(D₁×D₂). An example shows that the lower and upper bounds are best possible. In particular, exact values of H_λ(D₁×D₂) are obtained in special cases. These results are also generalized to the cartesian product of n strongly connected digraphs.     

A Broadcasting Protocol in Line Digraphs

We propose broadcasting algorithms for line digraphs in the telegraph model. The new protocols use a broadcasting protocol for a graph G to obtain a broadcasting protocol for the graph L^kG, the graph obtained by applying k times, the line digraph operation to G. As a consequence improved bounds for the broadcasting time in De Bruijn, Kautz, and Wrapped Butterfly digraphs are obtained.     

The twin domination number in generalized de Bruijn digraphs

Let G=(V,A) be a digraph. A set T of vertices of G is a twin dominating set of G if for every vertex v∈V?T, there exist u,w∈T (possibly u=w) such that arcs (u,v),(v,w)∈A. The twin domination numberγ^∗(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we investigate the twin domination number in generalized de Bruijn digraphs GB(n,d). For the digraphs GB(n,d), we first establish sharp bounds on the twin domination number. Secondly, we give the exact values of the twin domination number for several types of GB(n,d) by constructing minimum twin dominating sets in the digraphs. Finally, we present sharp upper bounds for some special generalized de Bruijn digraphs.     

On the k-tuple domination of generalized de Brujin and Kautz digraphs

A vertex u in a digraph G = (V, A) is said to dominate itself and vertices v such that (u, v) ∈ A. For a positive integer k, a k-tuple dominating set of G is a subset D of vertices such that every vertex in G is dominated by at least k vertices in D. The k-tuple domination number of G is the minimum cardinality of a k-tuple dominating set of G. This paper deals with the k-tuple domination problem on generalized de Bruijn and Kautz digraphs. We establish bounds on the k-tuple domination number for the generalized de Bruijn and Kautz digraphs and we obtain some conditions for the k-tuple domination number attaining the bounds.     

Improved Algorithms for Even Factors and Square-Free Simple b-Matchings

Given a digraph G=(VG,AG), an even factor M?AG is a set formed by node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geelen and Cunningham and generalize path matchings in undirected graphs. Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard but for the class of odd-cycle symmetric digraphs the problem is polynomially solvable. So far the only combinatorial algorithm known for this task is due to Pap; its running time is O(n ⁴) (hereinafter n denotes the number of nodes in G and m denotes the number of arcs or edges). In this paper we introduce a novel sparse recovery technique and devise an O(n ³logn)-time algorithm for finding a maximum cardinality even factor in an odd-cycle symmetric digraph. Our technique also applies to other similar problems, e.g. finding a maximum cardinality square-free simple b-matching.     

On the k-tuple domination of de Bruijn and Kautz digraphs

In a digraph G, a vertex u is said to dominate itself and vertices v such that (u,v) is an arc of G. For a positive integer k, a k-tuple dominating set D of a digraph is a subset of vertices such that every vertex is dominated by at least k vertices in D. The k-tuple domination number of a given digraph is the minimum cardinality of a k-tuple dominating set of the digraph. In this letter, we give the exact values of the k-tuple domination number of de Bruijn and Kautz digraphs.     

Minimal proper interval completions

Given an arbitrary graph G=(V,E) and a proper interval graph H=(V,F) with E⊆F we say that H is a proper interval completion of G. The graph H is called a minimal proper interval completion of G if, for any sandwich graph H^′=(V,F^′) with E⊆F^′⊂F, H^′ is not a proper interval graph. In this paper we give a O(n+m) time algorithm computing a minimal proper interval completion of an arbitrary graph. The output is a proper interval model of the completion.     

Vertex fault tolerance of optimal-κ graphs and super-κ graphs

A connected graph G is optimal-κ if κ(G)=δ(G). It is super-κ if every minimum vertex cut isolates a vertex. An optimal-κ graph G is m-optimal-κ if for any vertex set S⊆V(G) with |S|?m, G−S is still optimal-κ. We define the vertex fault tolerance with respect to optimal-κ, denoted by Oκ(G), as the maximum integer m such that G is m-optimal-κ. The concept of vertex fault tolerance with respect to super-κ, denoted by Sκ(G), is defined in a similar way. In this paper, we show that min{κ₁(G)−δ(G),δ(G)−1}?Oκ(G)?δ(G)−1 and min{κ₁(G)−δ(G)−1,δ(G)−1}?Sκ(G)?δ(G)−1, where κ₁(G) is the 1-extra connectivity of G. Furthermore, when the graph is triangle free, more refined lower bound can be derived for Oκ(G).     

The possible cardinalities of global secure sets in cographs

Let G=(V,E) be a graph. A global secure set SD⊆V is a dominating set which also satisfies a condition that |N[X]∩SD|≥|N[X]−SD| for every subset X⊆SD. The minimum cardinality of the global secure set in the graph G is denoted by γ_s(G). In this paper, we introduce the notion of γ_s-monotone graphs. The graph G is γ_s-monotone if, for every k∈{γ_s(G),γ_s(G)+1,…,n}, it has a global secure set of cardinality k. We will also present the results concerning the minimum cardinality of the global secure sets in the class of cographs.     

Minimum Cost Source Location Problems with Flow Requirements

In this paper, we consider source location problems and their generalizations with three connectivity requirements (arc-connectivity requirements λ and two kinds of vertex-connectivity requirements κ and ), where the source location problems are to find a minimum-cost set S⊆V in a given graph G=(V,A) with a capacity function u:A→ℝ₊ such that for each vertex v∈V, the connectivity from S to v (resp., from v to S) is at least a given demand d ⁻(v) (resp., d ⁺(v)). We show that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard, which solves an open problem posed by Arata et al. (J. Algorithms 42: 54–68, 2002). Moreover, we show that the source location problems with three connectivity requirements are inapproximable within a ratio of cln D for some constant c, unless every problem in NP has an O(N ^{log log N} )-time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. By the inapproximable results above, this implies that all the source location problems are Θ(ln ∑ _v∈V (d ⁺(v)+d ⁻(v)))-approximable. An extended abstract of this paper appeared in Sakashita et al. (Proceedings of LATIN 2006, Chile, LNCS, vol. 3887, pp. 769–780, March 2006).     

A note on the inapproximability of correlation clustering

We consider inapproximability of the correlation clustering problem defined as follows: Given a graph G=(V,E) where each edge is labeled either “+” (similar) or “−” (dissimilar), correlation clustering seeks to partition the vertices into clusters so that the number of pairs correctly (resp., incorrectly) classified with respect to the labels is maximized (resp., minimized). The two complementary problems are called MaxAgree and MinDisagree, respectively, and have been studied on complete graphs, where every edge is labeled, and general graphs, where some edge might not have been labeled. Natural edge-weighted versions of both problems have been studied as well. Let S-MaxAgree denote the weighted problem where all weights are taken from set S, we show that S-MaxAgree with weights bounded by O(|V|^1/2−δ) essentially belongs to the same hardness class in the following sense: if there is a polynomial time algorithm that approximates S-MaxAgree within a factor of λ=O(log|V|) with high probability, then for any choice of S^′, S^′-MaxAgree can be approximated in polynomial time within a factor of (λ+?), where ?>0 can be arbitrarily small, with high probability. A similar statement also holds for S-MinDisagree. This result implies it is hard (assuming NP≠RP) to approximate unweighted MaxAgree within a factor of 80/79−?, improving upon a previous known factor of 116/115−? by Charikar et al. [M. Charikar, V. Guruswami, A. Wirth, Clustering with qualitative information, Journal of Computer and System Sciences 71 (2005) 360-383].¹     

Absorbant of generalized de Bruijn digraphs

The generalized de Bruijn digraph GB(n,d) has good properties as an interconnection network topology. The resource location problem in an interconnection network is one of the facility location problems. Finding absorbants of a digraph corresponds to solving a kind of resource location problem. In this paper, we establish bounds on the absorbant number for GB(n,d), and we give some sufficient conditions for the absorbant number of GB(n,d) to achieve the bounds. When d divides n, the extremal digraphs achieving the upper bound are characterized by determining their absorbants.     

Super-connected and super-arc-connected Cartesian product of digraphs

We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained:

(i)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=κ(Di) for i=1,2, then D₁×D₂ is super-κ if and only if ,

(ii)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=λ(Di) for i=1,2, then D₁×D₂ is super-λ if and only if ,

where λ(D)=δ(D)=1, denotes the complete digraph of order n and n?2.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes

A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to |V(G)| inclusive. It has been shown that Q_n is bipancyclic if and only if n?2. In this paper, we improve this result by showing that every edge of Q_n−E′ lies on a cycle of every even length from 4 to |V(G)| inclusive where E′ is a subset of E(Q_n) with |E′|?n−2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length l joining any two different vertices x and y of Q_n when h(x,y)?l?|V(G)|−1 and l−h(x,y) is even where h(x,y) is the Hamming distance between x and y.