The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numeric...The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.展开更多
After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number ...After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring.展开更多
In this paper, the half-strong endomorphisms of the join of split graphs are investigated. We give the conditions under which the half-strong endomorphisms of the join of split graphs form a monoid.
In this paper,the half-strong,the locally strong and the quasi-strong endomorphisms of a split graph are investigated.Let X be a split graph and let End(X),hEnd(X),lEnd(X) and qEnd(X) be the endomorphism monoid,the se...In this paper,the half-strong,the locally strong and the quasi-strong endomorphisms of a split graph are investigated.Let X be a split graph and let End(X),hEnd(X),lEnd(X) and qEnd(X) be the endomorphism monoid,the set of all half-strong endomorphisms,the set of all locally strong endomorphisms and the set of all quasi-strong endomorphisms of X,respectively.The conditions under which hEnd(X) forms a submonoid of End(X) are given.It is shown that lEnd(X) = qEnd(X) for any split graph X.The conditions under which lEnd(X)(resp.qEnd(X)) forms a submonoid of End(X) are also given.In particular,if hEnd(X) forms a monoid,then lEnd(X)(resp.qEnd(X)) forms a monoid too.展开更多
Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we...Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we prove root square mean labeling of some degree splitting graphs.展开更多
In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admi...In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admits a Zero-M-Cordial labeling. Further we prove that Kn × P2Bn = K1,n × P2 of odd n admits a Zero-M-Cordial labeling.展开更多
In this paper we prove that the join of two path graphs, two cycle graphs, Ladder graph and the tensor product are H2-cordial labeling. Further we prove that the join of two wheel graphs Wn and Wm, (mod 4) admits a H-...In this paper we prove that the join of two path graphs, two cycle graphs, Ladder graph and the tensor product are H2-cordial labeling. Further we prove that the join of two wheel graphs Wn and Wm, (mod 4) admits a H-cordial labeling.展开更多
In this paper we prove that the split graphs of K1,n and Bn,n are prime cordial graphs. We also show that the square graph of Bn,n is a prime cordial graph while middle graph of Pn is a prime cordial graph for n≥4 . ...In this paper we prove that the split graphs of K1,n and Bn,n are prime cordial graphs. We also show that the square graph of Bn,n is a prime cordial graph while middle graph of Pn is a prime cordial graph for n≥4 . Further we prove that the wheel graph Wn admits prime cordial labeling for n≥8.展开更多
Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
基金Supported by the National Natural Science Foundation of China（11101383） Supported by the Natural Science Foundation of Henan Province（112300410047）
文摘The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.
基金Supported by the National Natural Science Foundation of China(No.11001196)
文摘After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring.
基金Supported by National Natural Science Foundation of China (Grant Nos. 10571077 and 10971053)
文摘In this paper, the half-strong endomorphisms of the join of split graphs are investigated. We give the conditions under which the half-strong endomorphisms of the join of split graphs form a monoid.
基金supported by National Natural Science Foundation of China(Grant Nos. 10571077,10971086)
文摘In this paper,the half-strong,the locally strong and the quasi-strong endomorphisms of a split graph are investigated.Let X be a split graph and let End(X),hEnd(X),lEnd(X) and qEnd(X) be the endomorphism monoid,the set of all half-strong endomorphisms,the set of all locally strong endomorphisms and the set of all quasi-strong endomorphisms of X,respectively.The conditions under which hEnd(X) forms a submonoid of End(X) are given.It is shown that lEnd(X) = qEnd(X) for any split graph X.The conditions under which lEnd(X)(resp.qEnd(X)) forms a submonoid of End(X) are also given.In particular,if hEnd(X) forms a monoid,then lEnd(X)(resp.qEnd(X)) forms a monoid too.
文摘Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we prove root square mean labeling of some degree splitting graphs.
文摘In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admits a Zero-M-Cordial labeling. Further we prove that Kn × P2Bn = K1,n × P2 of odd n admits a Zero-M-Cordial labeling.
文摘In this paper we prove that the join of two path graphs, two cycle graphs, Ladder graph and the tensor product are H2-cordial labeling. Further we prove that the join of two wheel graphs Wn and Wm, (mod 4) admits a H-cordial labeling.
文摘In this paper we prove that the split graphs of K1,n and Bn,n are prime cordial graphs. We also show that the square graph of Bn,n is a prime cordial graph while middle graph of Pn is a prime cordial graph for n≥4 . Further we prove that the wheel graph Wn admits prime cordial labeling for n≥8.
文摘Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
