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.展开更多
In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the disting...In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.展开更多
For a ring R(not necessarily commutative)with identity,the comaximal graph of R,denoted byΩ(R),is a graph whose vertices are all the nonunit elements of R,and two distinct vertices a and b are adjacent if and only if...For a ring R(not necessarily commutative)with identity,the comaximal graph of R,denoted byΩ(R),is a graph whose vertices are all the nonunit elements of R,and two distinct vertices a and b are adjacent if and only if Ra+Rb=R.In this paper we consider a subgraphΩ_(1)(R)ofΩ(R)induced by R\Uℓ(R),where Uℓ(R)is the set of all left-invertible elements of R.We characterize those rings R for whichΩ_(1)(R)\J(R)is a complete graph or a star graph,where J(R)is the Jacobson radical of R.We investigate the clique number and the chromatic number of the graphΩ_(1)(R)\J(R),and we prove that if every left ideal of R is symmetric,then this graph is connected and its diameter is at most 3.Moreover,we completely characterize the diameter ofΩ_(1)(R)\J(R).We also investigate the properties of R whenΩ_(1)(R)is a split graph.展开更多
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 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.
文摘In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.
基金This research was supported by NSFC(12071484,11871479)Hunan Provincial Natural Science Foundation(2020JJ4675,2018JJ2479)the Research Fund of Beijing Information Science and Technology University(2025030).
文摘For a ring R(not necessarily commutative)with identity,the comaximal graph of R,denoted byΩ(R),is a graph whose vertices are all the nonunit elements of R,and two distinct vertices a and b are adjacent if and only if Ra+Rb=R.In this paper we consider a subgraphΩ_(1)(R)ofΩ(R)induced by R\Uℓ(R),where Uℓ(R)is the set of all left-invertible elements of R.We characterize those rings R for whichΩ_(1)(R)\J(R)is a complete graph or a star graph,where J(R)is the Jacobson radical of R.We investigate the clique number and the chromatic number of the graphΩ_(1)(R)\J(R),and we prove that if every left ideal of R is symmetric,then this graph is connected and its diameter is at most 3.Moreover,we completely characterize the diameter ofΩ_(1)(R)\J(R).We also investigate the properties of R whenΩ_(1)(R)is a split graph.
基金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.
