共查询到20条相似文献,搜索用时 0 毫秒
1.
Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C2□Cn)=n; γ(C3□Cn)=n if , otherwise, γ(C3□Cn)=n+1; if , otherwise, . 相似文献
2.
Domination number of Cartesian products of directed cycles 总被引:1,自引:0,他引:1
Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In Liu et al. (2010) [11], we determined the exact values of γ(Cm□Cn) when m=2,3,4. In this paper, we give a lower and upper bounds for γ(Cm□Cn). Furthermore, we prove a necessary and sufficient conditions for Cm□Cn to have an efficient dominating set. Also, we determine the exact values: γ(C5□Cn)=2n; γ(C6□Cn)=2n if n≡0(mod 3), otherwise, γ(C6□Cn)=2n+2; if m≡0(mod 3) and n≡0(mod 3). 相似文献
3.
Sandi Klavžar 《国际计算机数学杂志》2015,92(4):694-699
A local colouring of a graph G is a function c: V(G)→? such that for each S ? V(G), 2≤|S|≤3, there exist u, v∈S with |c(u)?c(v)| at least the number of edges in the subgraph induced by S. The maximum colour assigned by c is the value χ?(c) of c, and the local chromatic number of G is χ?(G)=min {χ?(c): c is a local colouring of G}. In this note the local chromatic number is determined for Cartesian products G □ H, where G and GH are 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that if G and H are graphs such that χ(G)≤? χ?(H)/2 ?, then χ?(G □ H)≤χ?(H)+1. 相似文献
4.
Performance modeling of Cartesian product networks 总被引:1,自引:0,他引:1
Reza MoravejiAuthor Vitae Hamid Sarbazi-AzadAuthor Vitae Albert Y. ZomayaAuthor Vitae 《Journal of Parallel and Distributed Computing》2011,71(1):105-113
This paper presents a comprehensive performance model for fully adaptive routing in wormhole-switched Cartesian product networks. Besides the generality of the model which makes it suitable to be used for any product graph, experimental (simulation) results show that the proposed model exhibits high accuracy even in heavy traffic and saturation region, where other models have severe problems to predict the performance of the network. Most popular interconnection network can be defined as a Cartesian product of two or more networks including the mesh, hypercube, and torus networks. Torus and mesh networks are the most popular topologies used in recent supercomputing parallel machines. They have been widely used for realizing on-chip network in recent on-chip multicore and multiprocessors system. 相似文献
5.
Hai-Yang Li Sheng-Gang Li Min-Hui Zhu 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(11):1115-1118
In the paper, we prove that is compatible with p}, the set of commutant of p, and , the projection commutant of a, are all normal sub-effect algebras of a compressible effect algebra E, and is a direct retraction on E} is a normal sub-effect algebra of an effect algebra E. Moreover, we answer an open question in Gudder’s (Rep Math Phys 54:93–114, 2004), Compressible effect algebras, Rep Math
Phys, by showing that the cartesian product of an infinite number of E
i
is a compressible effect algebra if and only if each E
i
is a compressible effect algebra.
This work was supported by the SF of Education Department of Shaanxi Province (Grant No. 07JK267), P. R. China. 相似文献
6.
The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of G−F for any F⊂V(G) with |F|<k. Krishnamoorthy and Krishnamurthy first proposed this concept and gave Dκ(G1)+κ(G2)(G1×G2)?Dκ(G1)(G1)+Dκ(G2)(G2) when κ(G1×G2)=κ(G1)+κ(G2), where κ(G) is the connectivity of G. This paper gives a counterexample to this bound and establishes Dk1+k2(G1×G2)?Dk1(G1)+Dk2(G2)+1 for any ki-connected graph Gi and ki?1 for i=1,2. 相似文献
7.
This paper considers the wavelength assignment problem for Cartesian product networks with multi-hops. An upper bound of the (uniform) wavelength index for Cartesian product networks with single-hop is established. This result leads to a consequence for the nth power of an arbitrary network with k-hops. In particular, if k=1, this bound partially generalizes the results of Pankaj [R.K. Pankaj, Architectures for linear lightwave networks, PhD thesis, Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, MA, 1992], Bermond et al. [J.-C. Bermond, L. Gargano, S. Perennes, A.A. Rescigno, U. Vaccaro, Efficient collective communication in optical networks, Theoret. Comput. Sci. 233 (2000) 165-189] and Beauquier [B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks, Networks 33 (1999) 179-187] for hypercubes and Hamming graphs. As an application, a tight upper bound for Hamming graph with k hops is established and a corresponding open problem is also proposed. 相似文献
8.
针对于模糊c-均值(FCM)算法在初始聚类中心选取不佳的情况下容易产生聚类错误划分的情况,从FCM算法出发提出了一种基于笛卡尔乘积的FCM聚类算法(C-FCM),并分析了加权指数m对聚类分析的影响。C-FCM将聚类提高到更高维的空间,有效地避免了FCM 对初值敏感及容易陷入局部极小的缺陷。客运专线列控(TCC)评估测试项目对C-FCM的检验结果表明,与传统FCM算法相比,C-FCM算法更准确,效果更佳,对解决邻站数据包的划分问题是可行、有效的。 相似文献
9.
《Journal of Computer and System Sciences》2016,82(5):767-781
Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to , where is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to , where . A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where , 9, let , be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of and . 相似文献
10.
11.
《国际计算机数学杂志》2012,89(3):522-526
A set S of vertices of a graph G is a dominating set for G if every vertex of G is adjacent to at least one vertex of S. The domination number γ(G), of G, is the minimum cardinality of a dominating set in G. Moreover, if the maximum degree of G is Δ, then for every positive integer k≤Δ, the set S is a k-dominating set in G if every vertex outside of S is adjacent to at least k vertices of S. The k-domination number of G, denoted by γ k (G), is the minimum cardinality of a k-dominating set in G. A map f: V→<texlscub>0, 1, 2</texlscub>is a Roman dominating function for G if for every vertex v with f(v)=0, there exists a vertex u∈N(v) such that f(u)=2. The weight of a Roman dominating function is f(V)=∑ u∈V f(u). The Roman domination number γR(G), of G, is the minimum weight of a Roman dominating function on G. In this paper, we obtain that for any two graphs G and H, the k-domination number of the Cartesian product of G and H is bounded below by γ(G)γ k (H)/2. Also, we obtain that the domination number of Cartesian product of G and H is bounded below by γ(G)γR(H)/3. 相似文献
12.
LetG be a connected graph withn vertices andm edges. We develop an algorithm that finds the (unique) prime factors ofG with respect to the Cartesian product inO(m logn) time andO(m) space. This shows that factoringG is at most as costly as sorting its edges. The algorithm gains its efficiency and practicality from using only basic properties of product graphs and simple data structures. 相似文献
13.
14.
Iztok Bani? 《Information Processing Letters》2006,100(2):47-51
Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let G be a kG-connected graph and Dc(G) denote the diameter of G after deleting any of its c<kG vertices. We prove that Da+b+1(G)?Da(F)+Db(B)+1 if G is a graph bundle with fibre F over base B, a<kF, and b<kB. 相似文献
15.
Xie-Bin Chen 《Information Processing Letters》2011,111(5):235-238
A set of k spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, one path in each spanning tree, are internally disjoint. Using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Thus, the problem of ISTs on graphs has been received much attention. Recently, Yang et al. proposed a parallel algorithm for generating optimal ISTs on the hypercube. In this paper, we propose a similar algorithm for generating optimal ISTs on Cartesian product of complete graphs. The algorithm can be easily implemented in parallel or distributed systems. Moreover, the proof of its correctness is simpler than that of Yang et al. 相似文献
16.
Pranava K. Jha 《Information Processing Letters》2003,87(3):163-168
If r?1, and m and n are each a multiple of (r+1)2+r2, then each isomorphic component of Cm×Cn admits of a vertex partition into (r+1)2+r2 perfect r-dominating sets. The result induces a dense packing of Cm×Cn by means of vertex-disjoint subgraphs, each isomorphic to a diagonal array. Areas of applications include efficient resource placement in a diagonal mesh and error-correcting codes. 相似文献
17.
18.
In 1992, Manoussakis conjectured that a strongly 2-connected digraph D on n vertices is hamiltonian if for every two distinct pairs of independent vertices x, y and w, z we have d(x)+d(y)+d(w)+d(z)≥4n−3. In this note we show that D has a Hamilton path, which gives an affirmative evidence supporting this conjecture. 相似文献
19.
Alberto Policriti 《Information Processing Letters》2011,111(16):787-791
Transitive sets with n elements were counted by Peddicord in 1962, by the use of Ackermann?s numeric encoding of a (hereditarily finite) set. In this paper we give a combinatorial interpretation of this number by counting extensional acyclic digraphs. In a similar constructive manner, we also obtain the number of weakly extensional acyclic digraphs with a given number of labeled sinks and a given number of sources, or with a given number of vertices of maximum rank. 相似文献
20.
Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络(又称圈图)、轮图等都既是Cayley图又是重要的互连网络。利用图的笛卡尔乘积方法构建了几类新的笛卡尔乘积互连网络:环网、循环移数网络、ILLIAC网络、超立方体分别与Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络、轮图的笛卡尔乘积网络;这些网络的某些性能指标(例如,直径等)比Star网络或超立方体更好。 相似文献