共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
3.
《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 . 相似文献
4.
《国际计算机数学杂志》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. 相似文献
5.
Sun-yuan Hsieh 《Information Processing Letters》2002,82(3):131-135
A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χr(G) is the smallest value of t such that G has a vertex t-ranking. A χr(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time. 相似文献
6.
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. 相似文献
7.
Juan Liu 《Information Processing Letters》2008,108(3):90-93
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 D1×D2 is super-κ if and only if ,
- (ii)
- If δ+(Di)=δ−(Di)=δ(Di)=λ(Di) for i=1,2, then D1×D2 is super-λ if and only if ,
8.
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, . 相似文献
9.
10.
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. 相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
针对于模糊c-均值(FCM)算法在初始聚类中心选取不佳的情况下容易产生聚类错误划分的情况,从FCM算法出发提出了一种基于笛卡尔乘积的FCM聚类算法(C-FCM),并分析了加权指数m对聚类分析的影响。C-FCM将聚类提高到更高维的空间,有效地避免了FCM 对初值敏感及容易陷入局部极小的缺陷。客运专线列控(TCC)评估测试项目对C-FCM的检验结果表明,与传统FCM算法相比,C-FCM算法更准确,效果更佳,对解决邻站数据包的划分问题是可行、有效的。 相似文献
14.
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. 相似文献
15.
Thomas Andreae Michael Nölle Gerald Schreiber 《Journal of Parallel and Distributed Computing》1997,46(2):531
Given a Cartesian productG=G1× … ×Gm(m≥ 2) of nontrivial connected graphsGiand then-dimensional baseBde Bruijn graphD=DB(n), it is investigated whether or notGis a spanning subgraph ofD. Special attention is given to graphsG1× … ×Gmwhich are relevant for parallel computing, namely, to Cartesian products of paths (grids) or cycles (tori). For 2-dimensional de Bruijn graphsD, we present a theorem stating that certain structural assumptions on the factorsG1, …,Gmensure thatG1× … ×Gmis a spanning subgraph ofD. As corollaries, we obtain results improving previous results of Heydemannet al.(J. Parallel Distrib. Comput.23 (1994), 104–111) on embedding grids and tori into de Bruijn graphs. Specifically, we obtain that (i) any gridG=G1× … ×Gmis a spanning subgraph ofD=DB(2) provided that |G| = |D|, and (ii) any torusG=G1× … ×Gmis a spanning subgraph ofD=DB(2) provided that |G| = |D| and that theGiare cycles of even length ≥4. We show that these results have consequences for the casen> 2, too: for evenn, we apply our results to obtain embeddings of grids and toriGinto de Bruijn graphsDB(n) with dilationn/2, where the baseBis a fixed integer ≥2, andnis big enough to ensure |G| ≤ |DB(n)|. We also contrast our results forn= 2 with nonexistence results forn≥ 3 and briefly describe experimental results in the area of parallel image processing. 相似文献
16.
现有的有向图聚类算法大多基于向量空间中节点间的近似线性关系假设,忽略了节点间存在的非线性相关性。针对该问题,提出一种基于核非负矩阵分解(KNMF)的有向图聚类算法。首先,引入核学习方法将有向图的邻接矩阵投影到核空间,并通过特定的正则项约束原空间及核空间中节点间的相似性。其次,提出了图正则化核非对称NMF算法的目标函数,并在非负约束条件下通过梯度下降方法推导出一个聚类算法。该算法在考虑节点连边的方向性的同时利用核学习方法建模节点间的非线性关系,从而准确地揭示有向图中潜在的结构信息。最后,在专利-引文网络(PCN)数据集上的实验结果表明,簇的数目为2时,和对比算法相比,所提算法将DB值和DQF值分别提高了约0.25和8%,取得了更好的聚类质量。 相似文献
17.
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). 相似文献
18.
Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络(又称圈图)、轮图等都既是Cayley图又是重要的互连网络。利用图的笛卡尔乘积方法构建了几类新的笛卡尔乘积互连网络:环网、循环移数网络、ILLIAC网络、超立方体分别与Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络、轮图的笛卡尔乘积网络;这些网络的某些性能指标(例如,直径等)比Star网络或超立方体更好。 相似文献
19.
《国际计算机数学杂志》2012,89(2):129-136
Cyclic bundle Hamiltonicity cbH(G) of a graph G is the minimal n for which there is an automorphism α of G such that the graph bundle C n □α G is Hamiltonian. We define an invariant I that is related to the maximal vertex degree of spanning trees suitably involving the symmetries of G and prove cbH(G)≤I≤cbH(G)+1 for any non-trivial connected graph G. 相似文献