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...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.展开更多
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 diagnosi...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 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)/α(...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.展开更多
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 ...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.展开更多
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 c...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 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...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 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 re...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 .展开更多
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...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.展开更多
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 g...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.展开更多
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 mea...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.展开更多
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...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.展开更多
基金This work was supported by the National Natural Science Foundation of China （Grant No. 61370001）.
文摘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.
基金the Foundation of Fujian Provincial Department of Science & Technology (No. 2006F5035)the National Natural Science Foundation of China (No. 60502047)
文摘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 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.
基金The first author is supported by Fundamental Research Funds for the Central Universi- ties （No. XDJK2013C060）, Chongqing Research Program of Application Foundation and Advanced Technology （No. cstc2014jcyjA00028） and Scientific Research Foundation for Doctors of Southwest University （No. SWUl12054）. The second author is supported by National Natural Science Foundation of China （No. 11271250）.
文摘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.
文摘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 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.
基金Supported by the Scientific Research Fund of Education Department of Hunan Province(08C518)
文摘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 .
基金National Natural Science Foundation of China(No.10971025)
文摘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.
文摘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.
文摘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.
基金Project supported by the Natural Science Foundation of Gausu Province (Grant Nos.3Z5051-A25-037, 0809RJZA017)the National Natural Science Foundation of China (Grant No.50877034)the Foundation of Lanzhou University of Technology(Grant No.0914ZX136)
文摘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.
