The convexity spectra of graphs |
| |
Authors: | Li-Da Tong |
| |
Institution: | a Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 804, Taiwan b Rahal Gdid, Malta |
| |
Abstract: | 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 numbercon(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, 1?a?n-2, and 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 n?3 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 n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k. |
| |
Keywords: | 05C12 05C20 05C35 |
本文献已被 ScienceDirect 等数据库收录! |
|