g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM＊ model

Diagnosability of a multiprocessor system is an important study topic. S. L. Peng, C. K. Lin, J. J. M. Tan, and L. H. Hsu [Appl. Math. Comput., 2012, 218（21）： 10406-10412] proposed a new measure for fault diagnosis of the system, which is called the 9-good-neighbor conditional diagnosability that restrains every fault-free node containing at least 9 fault-free neighbors. As a famous topological structure of intereonnection networks, the n-dimensional star graph Sn has many good properties. In this paper, we establish the 9_good-neighbor conditional diagnosability of Sn under the PMC model and MM＊ model.

Diagnosability of the Incomplete Star Graphs

The growing size of the multiprocessor systems increases their vulnerability to component failures. It is crucial to local and to replace the fault processors to maintain system’s high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. This paper establishes the diagnosabilities of the incomplete star graph Sn (n≥4) with missing links under the PMC model and its variant, the BGM model, and shows that the diagnosabilities of incomplete star graph Sn under these two diagnostic models can be determined by the minimum degree of its topology structure. This method can also be applied to the other existing multiprocessor systems.

A necessary and sufficient condition for a vertex-transitive graph to be star extremal

A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. We first give a necessary and sufficient condition for a graph G to have circular chromatic number V(G)/α(G) (where V(G) is the vertex number of G and α(G) is its independence number). From this result, we get a necessary and sufficient condition for a vertex-transitive graph to be star extremal as well as a necessary and sufficient condition for a circulant graph to be star extremal. Using these conditions, we obtain several classes of star extremal graphs.

Artinian Local Rings Whose Annihilating-ideal Graphs Are Star Graphs

In this paper, a necessary and sufficient condition is given for a commutative Artinian local ring whose annihilating-ideal graph is a star graph. Also, a complete char- acterization is established for a finite local ring whose annihilating-ideal graph is a star graph.

组合星图(Com-Star Graph)网络拓扑结构的分解

本文从图论的角度对一种重要的且有意义的网络拓扑——组合星图（ｃｏｍ－ｓｔａｒｇｒａｐｈ）网络的结构问题进行研究。首先，定义了组合星图之后，给出了星图是组合星图的子结构的结论。其次，在给出组合图、排列图、１－因子分解等定义的基础上，分别讨论了组合星图的水平结构分解、子组合星图分解及１－因子分解等结论，并给予了证明。最后，结合图论中的边着色问题提出１－因子分解和边着色的联系，并给出特殊情况下组合星图的边着色的算法。

A Class of Star Extremal Circulant Graphs

The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. A graph is called star extremal if its fractional chromatic number equals to its circular chromatic number (also known as the star chromatic number). This paper studies the star extremality of the circulant graphs whose generating sets are of the form {±1,±k} .

The Star-Extremality of Circulant Graphs

The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph. We say a graph G is star extremal if its circular chromatic number is equal to its fractional chromatic number. This paper gives an improvement of a theorem. And we show that several classes of circulant graphs are star extremal.

The Crossing Number of Cartesian Products of Stars with 5-vertex Graphs II

The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those results, and determine the crossing numbers of cartesian products of two 5-vertex graphs with star K 1,n .

On k-Star Arboricity of Graphs

A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa（ G）,is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k ＋ 1. The k-star arboricity of a graph G,denoted by sak（ G）,is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2（ G） ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T）/k]t≤ sak（ T） ≤[Δ（ T）- 1/K]＋1,where Δ（ T） is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak（ T） ≤m for any tree T and any positive integers m and k.

Star网络S_6的Hamilton圈分解

Star网络Sn作为超立方体(一种著名互连网络)的替代品而被许多作者研究.与超立方体相比较,该网络有较小的直径和顶点度.在本文中,我们证明了关于Star网络Sn的一个猜想当n=6时是正确的,即S6是两个边不交的Hamilton圈及一个完美对集的并.

基于图论节点的改进A-star栅格路径规划算法

提出了一种将图论最短问题中的路径节点及栅格地图中的栅格节点位置信息结合的路径规划算法。依据图论最短问题思想,提取室内具有特殊信息的位置节点,并判断节点间可视性,加入到先决地图信息中。在此基础上改进的A-star算法在扩展节点时,根据启发函数,只在特殊节点位置进行扩展,避免计算大量不必要栅格点的启发函数,从而提高算法效率。实验结果表明,改进后的A-star算法较之前时间缩短了79.2%,所遍历栅格节点减少了99.4%,且栅格分辨率大小不影响路径规划效率。最后总结改进方法的优缺点,期望改进算法可用于室内多目标同时导航。

一类关联图的Star Extremal性质(英文)

证明了Cn的关联图I(Cn)是循环图,还证明了所有Cn的关联图I(Cn)及一些与I(Cn)有关的图是starextremal的.并用一种同构的方法得到了它们的圆色数和分色数.

Star图互连网络的容错性分析

限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数 .当考察这两个参数时 ,总假设网络中和一台计算机相连接的所有计算机不会同时出现故障 .该文证明了 Star图互连网络的极小分离集和极小限制分离集的唯一性 ,然后得到了 Star图的限制连通度是 2 n- 4,当 n=3,5和 n≥ 7时 ,它的限制容错直径是 | - 3( n- 1 ) /2 - | + 2 ,对于 n=4,6,限制容错直径是| - 3( n- 1 ) /2 - | + 3,即限制容错直径只比它的容错直径大 1 .

Starants: A New Model for Human Networks

In this paper, we will explain the relevance of the starant graphs, graphs created by us in the year of 2002. They were basically circulant graphs with a star graph that connects to all the vertices of the circulant graphs from inside of them, but they did not exist as a separate object of study in the year of 2002, as for all we knew. We now know that they can be used to model even social networking interactions, and they do that job better than any other graph we could be trying to use there. With the development of our mathematical tools, lots of conclusions will be made much more believable and therefore will become much more likely to get support from the relevant industries when attached to new queries.

Mean Cordial Labeling of Graphs

Let f be a map from V(G) to . For each edge uv assign the label . f is called a mean cordial la- beling if and , , where and denote the number of vertices and edges respectively labelled with x ( ). A graph with a mean cordial labeling is called a mean cor- dial graph. We investigate mean cordial labeling behavior of Paths, Cycles, Stars, Complete graphs, Combs and some more standard graphs.

Double quasi-star tree is determined by its Laplacian spectrum

Let Hn（p,q） be a tree obtained from two stars K1,p and K1,q by identifying the center of K1,p with one end of a path Pn and the center of K1,q with the other end of Pn.We call Hn（p,p-1） a double quasi-star tree.In this paper,we show that a double quasi-star tree is determined by its Laplacian spectrum.

一类仙人掌图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’_(st)(G)表示图G有星边染色的最小颜色数.仙人掌图是一个连通图使得每个块是圈或者边.利用数学归纳法得到了一类仙人掌图C_(n)·C_(m)(n≥3,m≥3)的星边色数,从而推广已知结果.

路与星图的强乘积图的容错直径

设路P_(m)与星图S_(1,n-1)的强乘积图为G=P_(m)S_(1,n-1).首先,通过归纳假设和构造内点或边不交路的方法,结合星图的中心性,给出图G的点容错直径D_(w)(G)和边容错直径D′t(G).结果表明,对图G中发生的任意点或边故障,都有D_(w)(G)≤d(G)+2,D′t(G)≤d(G)+1.其次,通过顶点数和边数构造的不等关系,给出两个极大连通图的强乘积图的点容错直径的上界,以及两个非平凡连通图的强乘积图的边容错直径的上界.

度为2的广义星图矩阵的逆特征值问题

运用两种不同的方法对度为2的广义星图矩阵(一种特殊类型的树的矩阵)的逆特征值问题进行了深入研究。首先,引入了一种标记这种树的顶点的方案,以便以多种特殊形式表示相应的矩阵。然后,针对给定的两类不同的特征数据,将此类矩阵的逆特征值问题转化为线性方程组求解问题,得到了所研究问题有唯一解的充分必要条件。最后,给出了矩阵唯一解的表达式和相应的算法。通过数值模拟实例验证了结果的准确性。

字典积图的任意可分性

给定n个顶点的图G,对于满足∑_(i=1)^(k)n_(i)=n的任意一个正整数序列(n_(1),n_(2),…,n_(k)),如果都存在顶点集V(G)的划分(V_(1),V_(2),…,V_(k)),满足Vi导出的子图G[V_(i)]是连通的,并且|V_(i)|=n_(i),其中1≤i≤k,则称图G是任意可分图(简称为AP).两个图G和H的字典积图记为G?H,其顶点集为V(G)×V(H),(g,h)(g,h)是G?H的一条边当且仅当gg∈E(G)或者g=g且hh∈E(H).讨论了可迹图和任意可分图的字典积图的任意可分性,证明了对于最大度至多为n+1的树T,如果T有一条路P满足全部度数为(T)的顶点属于顶点集V(P),则字典积图T○Pn是任意可分图;如果G是一个可迹图且H是任意可分图,则图G○H是任意可分图;如果G=S(2,a,b)是一个满足2≤a≤b的任意可分星型树,则图G○G是任意可分图;如果G是哈密顿图且H是一个图,则G○H是任意可分图.