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.展开更多
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.展开更多
.The intersection power graph of a finite group G is a simple graph whose vertex set is G,in which two distinct vertices and y are adjacent if and only if either one of a and y is the identity element,or(a)n(y)is non-....The intersection power graph of a finite group G is a simple graph whose vertex set is G,in which two distinct vertices and y are adjacent if and only if either one of a and y is the identity element,or(a)n(y)is non-trivial.A number of important graph classes,including cographs,chordal graphs,split graphs,and threshold graphs,can be defined either structurally or in terms of forbidden induced subgraphs.In this paper,we characterize the finite groups whose intersection power graphs are cographs,split graphs,and threshold graphs.We also classify the finite nilpotent groups whose intersection power graphs are chordal.展开更多
In this paper, split graphs with complete endomorphism-regularity are characterized explicitly. Hopefully, the main idea of the proofs can also be used for other classes of graphs.
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）, 1End（X） and qEnd（X） be the endomorphism ...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）, 1End（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 1End（X） = qEnd（X） for any split graph X. The conditions under which 1End（X） （resp. qEnd（X）） forms a submonoid of End（X） are also given. In particular, if hEnd（X） forms a monoid, then 1End（X） （resp. qEnd（X）） forms a monoid too.展开更多
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 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.展开更多
We introduce an innovative approach to address a significant challenge in interaction recognition,specificallythe capture of correlation features between different interaction body parts.These features are oftenoverlo...We introduce an innovative approach to address a significant challenge in interaction recognition,specificallythe capture of correlation features between different interaction body parts.These features are oftenoverlooked by traditional graph convolution networks commonly used in interaction recognition tasks.Oursolution,the Merge-and-Split Graph Convolutional Network,takes a unique perspective,treating interactionrecognition as a global problem.It leverages a Merge-and-Split Graph structure to effectively capturedependencies between interaction body parts.To extract the essential interaction features,we introducethe Merge-and-Split Graph Convolution module,which seamlessly combines the Merge-and-Split Graphwith Graph Convolutional Networks.This fusion enables the extraction of rich semantic information betweenadjacent joint points.In addition,we introduce a Short-term Dependence module designed to extract jointand motion characteristics specific to each type of interaction.Furthermore,to extract correlation featuresbetween different hierarchical sets,we present the Hierarchical Guided Attention Module.This module playsa crucial role in highlighting the relevant hierarchical sets that contain essential interaction information.The effectiveness of our proposed model is demonstrated by achieving state-of-the-art performance on 2widely recognized datasets,namely,the NTU60 and NTU120 interaction datasets.Our model’s efficacy isrigorously validated through extensive experiments,and we have made the code available for the researchcommunity at https://github.com/wanghq05/MS-GCN/.展开更多
基金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 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(Grant Nos.11801441,61976244)the Natural Science Basic Research Program of Shaanxi(Program No.2020JQ-761)the Shaanxi Fundamental Science Research Project for Mathematics and Physics(Grant No.22JSQ024).
文摘.The intersection power graph of a finite group G is a simple graph whose vertex set is G,in which two distinct vertices and y are adjacent if and only if either one of a and y is the identity element,or(a)n(y)is non-trivial.A number of important graph classes,including cographs,chordal graphs,split graphs,and threshold graphs,can be defined either structurally or in terms of forbidden induced subgraphs.In this paper,we characterize the finite groups whose intersection power graphs are cographs,split graphs,and threshold graphs.We also classify the finite nilpotent groups whose intersection power graphs are chordal.
文摘In this paper, split graphs with complete endomorphism-regularity are characterized explicitly. Hopefully, the main idea of the proofs can also be used for other classes of graphs.
基金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）, 1End（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 1End（X） = qEnd（X） for any split graph X. The conditions under which 1End（X） （resp. qEnd（X）） forms a submonoid of End（X） are also given. In particular, if hEnd（X） forms a monoid, then 1End（X） （resp. qEnd（X）） forms a monoid too.
基金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.
文摘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.
基金funding from the NationalNatural Science Foundation of China under Grant.No.62073004support from the Shenzhen Fundamental ResearchProgram under Grants.No.GXWD20201231165807007-20200807164903001 and JCYJ20200109140410340.
文摘We introduce an innovative approach to address a significant challenge in interaction recognition,specificallythe capture of correlation features between different interaction body parts.These features are oftenoverlooked by traditional graph convolution networks commonly used in interaction recognition tasks.Oursolution,the Merge-and-Split Graph Convolutional Network,takes a unique perspective,treating interactionrecognition as a global problem.It leverages a Merge-and-Split Graph structure to effectively capturedependencies between interaction body parts.To extract the essential interaction features,we introducethe Merge-and-Split Graph Convolution module,which seamlessly combines the Merge-and-Split Graphwith Graph Convolutional Networks.This fusion enables the extraction of rich semantic information betweenadjacent joint points.In addition,we introduce a Short-term Dependence module designed to extract jointand motion characteristics specific to each type of interaction.Furthermore,to extract correlation featuresbetween different hierarchical sets,we present the Hierarchical Guided Attention Module.This module playsa crucial role in highlighting the relevant hierarchical sets that contain essential interaction information.The effectiveness of our proposed model is demonstrated by achieving state-of-the-art performance on 2widely recognized datasets,namely,the NTU60 and NTU120 interaction datasets.Our model’s efficacy isrigorously validated through extensive experiments,and we have made the code available for the researchcommunity at https://github.com/wanghq05/MS-GCN/.
