http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : Kanté (검색결과 2 건)
- 무료
- 기관 내 무료
- 유료
-
-
Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions
Kanté,, Mamadou Moustapha,Kwon, O-joung Academic Press 2018 European journal of combinatorics Vol.74 No.-
<P><B>Abstract</B></P> <P>In the companion paper (Adler et al., 2017), we presented a characterization of the linear rank-width of distance-hereditary graphs, from which we derived an algorithm to compute it in polynomial time. In this paper, we investigate structural properties of distance-hereditary graphs based on this characterization.</P> <P>First, we prove that for a fixed tree T , every distance-hereditary graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . We extend this property to bigger graph classes, namely, classes of graphs whose prime induced subgraphs have bounded linear rank-width. Here, prime graphs are graphs containing no splits. We conjecture that for every tree T , every graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . Our result implies that it is sufficient to prove this conjecture for prime graphs.</P> <P>For a class Φ of graphs closed under taking vertex-minors, a graph G is called a <I>vertex-minor obstruction</I> for Φ if G ∉ Φ but all of its proper vertex-minors are contained in Φ . Secondly, we provide, for each k ⩾ 2 , a set of distance-hereditary graphs that contains all distance-hereditary vertex-minor obstructions for graphs of linear rank-width at most k . Also, we give a simpler way to obtain the known vertex-minor obstructions for graphs of linear rank-width at most 1.</P>
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
