共查询到20条相似文献,搜索用时 31 毫秒
1.
A k-containerC(u,v) of a graph G is a set of k disjoint paths joining u to v. A k-container C(u,v) is a k∗-container if every vertex of G is incident with a path in C(u,v). A bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u, v from different partite set of G. A bipartite graph G with connectivity k is super laceable if it is i∗-laceable for all i?k. A bipartite graph G with connectivity k is f-edge fault-tolerant super laceable if G−F is i∗-laceable for any 1?i?k−f and for any edge subset F with |F|=f<k−1. In this paper, we prove that the hypercube graph Qr is super laceable. Moreover, Qr is f-edge fault-tolerant super laceable for any f?r−2. 相似文献
2.
The super spanning connectivity and super spanning laceability of the enhanced hypercubes 总被引:1,自引:1,他引:0
Chung-Hao Chang Cheng-Kuan Lin Jimmy J. M. Tan Hua-Min Huang Lih-Hsing Hsu 《The Journal of supercomputing》2009,48(1):66-87
A k
-container
C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k
*
-container if it contains all vertices of G. A graph G is k
*
-connected if there exists a k
*-container between any two distinct vertices of G. Therefore, a graph is 1*-connected (respectively, 2*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k
*-container between any two distinct vertices of G for every k with 1≤k≤κ(G) where κ(G) is the connectivity of G. A bipartite graph G is k
*
-laceable if there exists a k
*-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k
*-container between any two vertices from different partite set of G for every k with 1≤k≤κ(G). In this paper, we prove that the enhanced hypercube Q
n,m
is super spanning laceable if m is an odd integer and super spanning connected if otherwise.
相似文献
Chung-Hao ChangEmail: |
3.
Meijie Ma 《Information Sciences》2010,180(17):3373-3379
A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQn is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2. 相似文献
4.
Ruijuan Li 《Information Processing Letters》2010,110(16):651-654
For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. In this paper, we show that if G is a ⌊3k/2⌋-connected graph of order n?100k, and d(u)+d(v)?n for any two vertices u and v with d(u,v)=2, then G is k-ordered hamiltonian. Our result implies the theorem of G. Chen et al. [Ars Combin. 70 (2004) 245-255] [1], which requires the degree sum condition for all pairs of non-adjacent vertices, not just those distance 2 apart. 相似文献
5.
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 (u1,v1) and (u2,v2) are adjacent in G×H if u1u2∈E(G) and v1v2∈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(2(n/logn)). 相似文献
6.
The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of an induced subgraph by deleting at most k−1 vertices from G. This paper considers the fault diameter of the product graph G1∗G2 of two graphs G1 and G2 and proves that Dk1+k2(G1∗G2)?Dk1(G1)+Dk2(G2)+1 if G1 is k1-connected and G2 is k2-connected. This generalizes some known results such as Bani? and ?erovnik [I. Bani?, J. ?erovnik, Fault-diameter of Cartesian graph bundles, Inform. Process. Lett. 100 (2) (2006) 47-51]. 相似文献
7.
In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u,v)∈A(G) are assigned colors c(u) and c(v), then for any (z,t)∈A(G), we cannot have simultaneously c(z)=c(v) and c(t)=c(u). The oriented chromatic number of an unoriented graph G is the smallest number k of colors for which any of the orientations of G can be colored with k colors.The main results we obtain in this paper are bounds on the oriented chromatic number of particular families of planar graphs, namely 2-dimensional grids, fat trees and fat fat trees. 相似文献
8.
Yan Sun 《国际计算机数学杂志》2015,92(3):441-450
Let m, j and k be positive integers. An m-circular-L(j, k)-labelling of a graph G is an assignment f from { 0, 1,?…?, m?1} to the vertices of G such that, for any two vertices u and v, |f(u)?f(v)|m≥j if uv∈E(G), and |f(u)?f(v)|m≥k if dG(u, v)=2, where |a|m=min{a, m?a}. The minimum m such that G has an m-circular-L(j, k)-labelling is called the circular-L(j, k)-labelling number of G. This paper determines the circular-L(2, 1)-labelling numbers of the direct product of a path and a complete graph and of the Cartesian product of a path and a cycle. 相似文献
9.
《国际计算机数学杂志》2012,89(9):1931-1939
Consider any undirected and simple graph G=(V, E), where V and E denote the vertex set and the edge set of G, respectively. Let |G|=|V|=n. The well-known Ore's theorem states that if degG(u)+degG(v)≥n+k holds for each pair of nonadjacent vertices u and v of G, then G is traceable for k=?1, hamiltonian for k=0, and hamiltonian-connected for k=1. Lin et al. generalized Ore's theorem and showed that under the same condition as above, G is r*-connected for 1≤r≤k+2 with k≥1. In this paper, we improve both theorems by showing that the hamiltonicity or r*-connectivity of any graph G satisfying the condition degG(u)+degG(v)≥n+k with k≥?1 is preserved even after one vertex or one edge is removed, unless G belongs to two exceptional families. 相似文献
10.
Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by η(G).Using algebraic methods we prove that η(G)?k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that η(T)?2 for every tree T, and η(G)?3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that for every planar graph G. Nevertheless we offer a provocative conjecture that η(G)?χ(G) for every graph G. 相似文献
11.
An edge ranking of a graph G is a labeling r of its edges with positive integers such that every path between two different edges eu, ev with the same rank r(eu)=r(ev) contains an intermediate edge ew with rank r(ew)>r(eu). An edge ranking of G is minimum if the largest rank k assigned is the smallest among all rankings of G. The edge ranking problem is to find a minimum edge ranking of given graph G. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of trees. In this paper, we first show, on a general graph G, a relation between a minimum edge ranking of G and its minimal cuts, which ensures that we can obtain a polynomial time algorithm for obtaining minimum edge ranking of a given graph G if minimal cuts for each subgraph of G can be found in polynomial time and the number of those is polynomial. Based on this relation, we develop a polynomial time algorithm for finding a minimum edge ranking on a 2-connected outerplanar graph. 相似文献
12.
Dejan Deli? 《Information Processing Letters》2010,110(16):662-665
Let k be a positive integer, and let G=(V,E) be a graph with minimum degree at least k−1. A function f:V→{−1,1} is said to be a signed k-dominating function (SkDF) if ∑u∈N[v]f(u)?k for every v∈V. An SkDF f of a graph G is minimal if there exists no SkDF g such that g≠f and g(v)?f(v) for every v∈V. The maximum of the values of ∑v∈Vf(v), taken over all minimal SkDFs f, is called the upper signed k-domination numberΓkS(G). In this paper, we present a sharp upper bound on this number for a general graph. 相似文献
13.
Shih-Yan Chen 《Computers & Electrical Engineering》2010,36(3):404-413
In 2000, Li et al. introduced dual-cube networks, denoted by DCn for n?1, using the hypercube family Qn and showed the vertex symmetry and some fault-tolerant hamiltonian properties of DCn. In this article, we introduce a new family of interconnection networks called dual-cube extensive networks, denoted by DCEN(G). Given any arbitrary graph G, DCEN(G) is generated from G using the similar structure of DCn. We show that if G is a nonbipartite and hamiltonian connected graph, then DCEN(G) is hamiltonian connected. In addition, if G has the property that for any two distinct vertices u,v of G, there exist three disjoint paths between u and v such that these three paths span the graph G, then DCEN(G) preserves the same property. Furthermore, we prove that the similar results hold when G is a bipartite graph. 相似文献
14.
《国际计算机数学杂志》2012,89(10):2212-2225
A Hamiltonian cycle C=? u 1, u 2, …, u n(G), u 1 ? with n(G)=number of vertices of G, is a cycle C(u 1; G), where u 1 is the beginning and ending vertex and u i is the ith vertex in C and u i ≠u j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C 1, C 2, …, C k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B n )=n?1 if n≥4, where B n is the n-dimensional bubble-sort graph. 相似文献
15.
A graph G∗ is 1-edge fault-tolerant with respect to a graph G, denoted by 1-EFT(G), if every graph obtained by removing any edge from G∗ contains G. A 1-EFT(G) graph is optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. The kth ladder graph, Lk, is defined to be the cartesian product of the Pk and P2 where Pn is the n-vertex path graph. In this paper, we present several 1-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal. 相似文献
16.
The diameter of a graph is an important factor for communication as it determines the maximum communication delay between any pair of processors in a network. Graham and Harary [N. Graham, F. Harary, Changing and unchanging the diameter of a hypercube, Discrete Applied Mathematics 37/38 (1992) 265-274] studied how the diameter of hypercubes can be affected by increasing and decreasing edges. They concerned whether the diameter is changed or remains unchanged when the edges are increased or decreased. In this paper, we modify three measures proposed in Graham and Harary (1992) to include the extent of the change of the diameter. Let D-k(G) is the least number of edges whose addition to G decreases the diameter by (at least) k, D+0(G) is the maximum number of edges whose deletion from G does not change the diameter, and D+k(G) is the least number of edges whose deletion from G increases the diameter by (at least) k. In this paper, we find the values of D-k(Cm), D-1(Tm,n), D-2(Tm,n), D+1(Tm,n), and a lower bound for D+0(Tm,n) where Cm be a cycle with m vertices, Tm,n be a torus of size m by n. 相似文献
17.
Virginia Vassilevska 《Information Processing Letters》2009,109(4):254-257
The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:
- •
- We give an algorithm for k-clique that runs in O(nk/(εlogn)k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.
- •
- Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u1,…,uk/2} and V={v1,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.
18.
Rao Li 《Information Processing Letters》2006,98(4):159-161
Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u)+d(v)+δ(u,v)?n+1 for each pair of distinct non-adjacent vertices u and v in G, where δ(u,v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad. 相似文献
19.
《Information and Computation》2007,205(7):1078-1095
Assume that G = (V, E) is an undirected graph, and C ⊆ V. For every v ∈ V, denote Ir(G; v) = {u ∈ C: d(u,v) ≤ r}, where d(u,v) denotes the number of edges on any shortest path from u to v in G. If all the sets Ir(G; v) for v ∈ V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r = 1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide. 相似文献
20.
We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β−1(u)−β−1(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)nO(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete. 相似文献