共查询到20条相似文献,搜索用时 10 毫秒
1.
An edge cut of a connected graph is m-restricted if its removal leaves every component having order at least m. The size of minimum m-restricted edge cuts of a graph G is called its m-restricted edge connectivity. It is known that when m≤4, networks with maximal m-restricted edge connectivity are most locally reliable. The undirected binary Kautz graph UK(2,n) is proved to be maximal 2- and 3-restricted edge connected when n≥3 in this work. Furthermore, every minimum 2-restricted edge cut disconnects this graph into two components, one of which being an isolated edge. 相似文献
2.
Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks
In transmission networks an important routing problem is to find a pair of link disjoint paths which optimises some performance measure. In this paper the problem of obtaining the most reliable pair of link disjoint paths, assuming the reliability of the links are known, is considered. This is a non-linear optimisation problem. It is further introduced the constraint that the length of the paths should not exceed a certain number of links, which makes the efficient resolution of the problem more complex. 相似文献
3.
For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant cD such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−cD if and only if for every n≥cD+3, has a cycle of order at least n−cD. Furthermore, we discuss some consequences and variants of this result. 相似文献
4.
Andrea Semani?ová 《Discrete Mathematics》2006,306(18):2263-2269
A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper, we characterize magic circulant graphs and 3-regular supermagic circulant graphs. We establish some conditions for supermagic circulant graphs. 相似文献
5.
We present a formula to enumerate non-isomorphic circulant digraphs of order n with connection sets of cardinality 2. This formula simplifies to C(n,2)=3×2a−1−4 in the case when n=2a(a≥3), and when n=pa(where p is an odd prime and a≥1). The number of non-isomorphic directed double networks are also enumerated. 相似文献
6.
On the Classification of Arc-transitive Circulant Digraphs of Order Odd-Prime-Squared 总被引:1,自引:0,他引:1
Xue Wen LI 《数学学报(英文版)》2005,21(5):1131-1136
A Cayley graph F = Cay(G, S) of a group G with respect to S is called a circulant digraph of order pk if G is a cyclic group of the same order. Investigated in this paper are the normality conditions for arc-transitive circulant (di)graphs of order p^2 and the classification of all such graphs. It is proved that any connected arc-transitive circulant digraph of order p^2 is, up to a graph isomorphism, either Kp2, G(p^2,r), or G(p,r)[pK1], where r|p- 1. 相似文献
7.
Edward Dobson 《Discrete Mathematics》2008,308(24):6047-6055
C.H. Li recently made the following conjecture: Let Γ be a circulant digraph of order n=n1n2 and degree m, where gcd(n1,n2)=1, n1 divides 4k, where k is odd and square-free, and every prime divisor of n2 is greater than m, or, if Γ is a circulant graph, every prime divisor of n2 is greater than 2m. Then Γ is a CI-digraph of Zn. In this paper we verify that this conjecture is true. 相似文献
8.
We characterize graphs of large enough order or large enough minimum degree which contain edge cuts whose deletion results in a graph with a specified number of large components. This generalizes and extends recent results due to Ou [Jianping Ou, Edge cuts leaving components of order at least m, Discrete Math. 305 (2005), 365-371] and Zhang and Yuan [Z. Zhang, J. Yuan, A proof of an inequality concerning k-restricted edge connectivity, Discrete Math. 304 (2005), 128-134]. 相似文献
9.
10.
Let be the circulant graph with . We study the reduced Euler characteristic of the independence complex for with prime and for with odd prime, proving that in both cases does not vanish. We also give an example of circulant graph whose independence complex has
which equals 0, giving a negative answer to R. Hoshino. 相似文献
11.
Connectivity of iterated line graphs 总被引:1,自引:0,他引:1
Yehong Shao 《Discrete Applied Mathematics》2010,158(18):2081-2087
Let k≥0 be an integer and Lk(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L2(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L2(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs. 相似文献
12.
限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数。当考察这两个参数时,总假设网络中和一台计算机相连接的所有计算机不会同时出现故障。该文证明了Star图互连网络的极小分离集和极小限制分离集的唯一性,然后得到了Star图的限制连通度是2n-4,当n=3,5和n≥7时,它的限制容错直径是|_3(n-1)/2_|+2,对于n =4, 6,限制容错直径是|_3(n-1)/2_|+3,即限制容错直径只比它的容错直径大1。 相似文献
13.
1.IntroductionAgraphG=(V,E)meansafinitegraphwithoutloopsandmultipleedgeswithvertexsetVandedgesetE,theclassicaledgeconnectivityA(G)ofGistheminimumsizeofasetUofedgessuchthatG--Uisdisconnected,andsuchasetUiscalledaoutsetofG.Notethatintheabovedefinition,absolutelynoconditionsorrestrictionsareimposedeitheronthecomponelltsofG--UoronthesetU.ThusitwouldseemnaturaltogeneralizetheconceptofedgeconnectivitybyintroducingsomeconditionsorrestrictionsonthecomponentsofG--Uand/orthesetU.Asageneralizatio… 相似文献
14.
We prove that a.a.s. as soon as a Kronecker graph becomes connected it has a finite diameter. 相似文献
15.
16.
17.
We classify trivalent vertex-transitive graphs whose edge sets have a partition into a Hamilton cycle and a 1-factor that is invariant under the action of the full automorphism group. 相似文献
18.
Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation 相似文献
19.
20.
Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture. 相似文献