The convexity spectra of graphs
- 作者：Li-Da Tong ; Pei-Lan Yen ; Alastair Farrugia
- 关键词：Convexity number ; Convex set ; Spectrum ; Oriented graph
- 刊名：Discrete Applied Mathematics
- 出版年：2008
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：28 May 2008
- 卷：156
- 期：10
- 页码：1838-1845
- 文件大小：174 K
摘要
Let D be a connected oriented graph. A set S
V(D) is convex in D if, for every pair of vertices x,y
S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity number con(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that SC(G)={con(D):D is an orientation of G} and SSC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n
4, 53c2316" title="Click to view the MathML source" alt="Click to view the MathML source">1
an-2, and c294d3eb973780d3dde5a1" title="Click to view the MathML source" alt="Click to view the MathML source">a≠2, there exists a 2-connected graph G with n vertices such that SC(G)=SSC(G)={a,n-1} and there is no connected graph G of order n3 with SSC(G)={n-1}. Then, we determine that SC(K3)={1,2}, SC(K4)={1,3}, SSC(K3)=SSC(K4)={1}, SC(K5)={1,3,4}, SC(K6)={1,3,4,5}, SSC(K5)=SSC(K6)={1,3}, SC(Kn)={1,3,5,6,…,n-1}, SSC(Kn)={1,3,5,6,…,n-2} for n7. Finally, we prove that, for any integers n, m, and k with 
, 1kn-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.
V(D) is convex in D if, for every pair of vertices x,yS, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity number con(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that SC(G)={con(D):D is an orientation of G} and SSC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n4, 53c2316" title="Click to view the MathML source" alt="Click to view the MathML source">1an-2, and c294d3eb973780d3dde5a1" title="Click to view the MathML source" alt="Click to view the MathML source">a≠2, there exists a 2-connected graph G with n vertices such that SC(G)=SSC(G)={a,n-1} and there is no connected graph G of order n3 with SSC(G)={n-1}. Then, we determine that SC(K3)={1,2}, SC(K4)={1,3}, SSC(K3)=SSC(K4)={1}, SC(K5)={1,3,4}, SC(K6)={1,3,4,5}, SSC(K5)=SSC(K6)={1,3}, SC(Kn)={1,3,5,6,…,n-1}, SSC(Kn)={1,3,5,6,…,n-2} for n7. Finally, we prove that, for any integers n, m, and k with kn-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.