Advanced
THE ORIENTABLE NUMBERS OF A GRAPH
THE ORIENTABLE NUMBERS OF A GRAPH
Journal of Applied Mathematics & Informatics. 2014. Sep, 32(3_4): 503-509
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : November 05, 2013
  • Accepted : February 20, 2014
  • Published : September 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
BYUNG KEE KIM

Abstract
For a connected graph G , there are orientations of G have different hull numbers, geodetic numbers, and convexity numbers. The lower orientable hull number h ( G ) is defined as the minimum hull number among all the orientations of G and the upper orientable hull number h + ( G ) as the maximum hull number among all the orientations of G . The lower and upper orientable geodetic numbers g ( G ) and h + ( G ) are defined similarily. In this paper, We investigate characterizations of the orientable numbers and the conditions that the relation h ( G ) ≤ g ( G ) < h + ( G ) ≤ g + ( G ) holds. AMS Mathematics Subject Classification : 05C12.
Keywords
1. Introduction
The distance d ( u, v ) between two vertices u and v in a connected graph G is the length of a shortest u v path in G . An u v path of length d ( u , v ) is called an u v geodesic. It is well known that this distance is a metric on the vertex set V ( G ). For more information, refer to [6]. We define I [ u , v ] to be the set of all vertices lying on some u v geodesic of G , and for a nonempty subset S of V ( G ), I [ S ] =
PPT Slide
Lager Image
The set S is convex if I [ S ] = S . Clearly, if S = { v } or S = V , then S is convex. The convexity number c ( G ) of G is the cardinality of a maximum proper convex subset of V . The convex hull [ S ] is the smallest convex set containing S . Since the intersection of two convex sets is convex, the convex hull is well defined. Note that S I [ S ] ⊆ [ S ] ⊆ V . A subset S V is called a geodetic set if I [ S ] = V and the geodetic number g ( G ) of G is the minimum cardinality of its geodetic sets. A subset S V is called a hull set if [ S ] = V and the hull number h ( G ) of G is the minimum cardinality of its hull sets. As a historical background, convexity in graphs was discussed in the book by Buckly and Harary [1] and studied by Harary and Niemenen [8] . The geodetic number of a graph was introduced by Chartrand et al. [3] , and studied by Chartrand et al. [4] and Kim [10]. Furthermore the hull number of a graph was introduced by Everett and Seidman [5] , and studied by Chartrand et al. [2] .
For an oriented graph D , the directed distance d ( u, v ) from a vertex u to a vertex v is the length of a shortest directed u v path. Although this distance is not a metric, as it clearly lacks the symmetry property, the above three numbers of D can be defined in a natural manner. A connected graph has orientations with different geodetic numbers and orientations with different hull numbers. Also a connected graph has orientations with different convexity numbers if there are no end-vertices. The aim of this paper is to survey characterizations of the three orientable numbers and their relations.
In the following we introduce some definitions used in directed graph. If the direction of the edge e in a directed graph is from vertex u to vertex v , then we write e = ( u, v ). The outdegree od ( v ) of a vertex v is the number of edges incident from v and indegree id ( v ) of a vertex v is the number of edges incident to v . A vertex u of a directed graph D is a transitive vertex if od ( u ) > 0, id ( u ) > 0, and for every ( x, u ), ( u, y ) ∈ E ( D ), ( x, y ) ∈ E ( D ). A vertex v of D is an extreme vertex if od ( v ) = 0, id ( v ) = 0, or a transitive vertex. A source(sink) of an oriented graph D is a vertex with idD ( v ) = 0 odD ( v ) = 0). Note that a vertex v is extreme iff V v is a convex set, iff v is contained in every hull set and every geodetic set.
For an undirected graph G , con ( G ) and con + ( G ) are the minimum and maximum convexity numbers over all orientations of G . We can make an arbitrary vertex v extreme by orienting all incident edges away from v for any graph G , so we always have con + ( G ) = n – 1, where n is the order of G . Moreover, if G contains an end-vertex x , then in every orientation x has indegree 0 or outdegree 0. So in this case, con ( G ) = n – 1 too. If G has no end-vextices, it is straightforward to find an orientation with no vertices indegree 0 or outdegree 0. A. Farrugia [7] was interested in whether con ( G ) < con + ( G ). We state his theorem.
Theorem 1.1. A graph with minimum degree 2 can be oriented so that all its vertices are non-extreme. Thus, for a connected graph G with at least 3 vertices, con ( G ) < con + ( G ) iff G has no end-vertices.
2. The relation h–(G) ≤ g–(G) < h+(G) ≤ g+(G)
In general, for a connected graph G , there are orientations of G that have distinct orientable numbers. This suggests the following definitions. For a connected graph G of order n ≥ 2, the lower orientable geodetic number g ( G ) is defined as the minimum geodetic number of an orientation of G and the upper orientable geodetic number g + ( G ) of G as the maximum such geodetic number, that is,
PPT Slide
Lager Image
Similarily, the lower orientable hull number h ( G ) and the upper orientable hull number h + ( G ) are defined. So we have
PPT Slide
Lager Image
Hence, for every connected graph G of order n ≥ 2, 2 ≤ g ( G ) ≤ g + ( G ) ≤ n and 2 ≤ h ( G ) ≤ h + ( G ) ≤ n .
Lemma 2.1. Let G be a complete graph of order n ≥ 2. then g ( G ) = 2 = h ( G ) and g + ( G ) = n = h + ( G ).
Proof . Let G be a complete graph with vertices v 1 , · · · , vn . We first orient G transitively (that is, ( vi , vj ) ∈ E ( G ) iff i < j ). Since every vertex is extreme, this orientation shows that g + ( G ) = n = h + ( G ). Reversing the orientation of v 1 v 2 · · · v n–1 vn makes { v 1 , v 2 } geodetic set. Thus g ( G ) = 2 = h ( G ).
G. Chartrand and P. Zhang [4] showed that if G is any connected graph of order n ≥ 3, then g ( G ) < g + ( G ).
Theorem 2.2. For any connected graph G of order n ≥ 3, then g ( G ) < g + ( G ).
Proof . We have already seen by Lemma 2.1 that the result is true if G is complete, so we can assume that G contains two vertices v 0 and v 2 with d ( v 0 , v 2 ) = 2. Let v 0 , v 1 , v 2 be a path of length 2 in G . Clearly, v 0 v 2 E ( G ). Let U = V ( G ) – { v 0 , v 1 , v 2 }. Since g ( P 3 ) ≠ g + ( P 3 ), we may assume that U ≠ ∅
To verify the result, it suffices to show that there exist two orientations of G having distinct geodetic numbers. An orientation D 1 of G is obtained by directing v 0 v 1 and v 1 v 2 so that ( v 0 , v 1 ), ( v 1 , v 2 ) ∈ E ( D 1 ). Every edge joining a vertex of U and v 0 is directed away from v 0 , while every edge joining a vertex of U and v 1 (or v 2 ) is directed toward v 1 (or v 2 ). The edges joining two vertices of U are directed arbitrarily. This completes the construction of D 1 . Since id D1 ( v 0 ) = od D1 ( v 2 ) = 0, the vertices v 0 and v 2 belong to every geodetic set of D 1 .
We now describe an orientation D 2 of G . First, we direct v 0 v 1 and v 1 v 2 so that ( v 0 , v 1 ), ( v 2 , v 1 ) ∈ E ( D 2 ). Every edge joining a vertex of U and v 1 is directed toward v 1 , while every edge joining a vertex of U and v 0 (or v 2 ) is directed away v 0 (or v 2 ). The edges joining two vertices of U are directed exactly as in the orientation D 1 . Since id D2 ( v 0 ) = od D2 ( v 1 ) = od D2 ( v 2 ) = 0, all of v 0 , v 1 , v 2 belong to every geodetic set of D 2 . Also, since I D2 [{ v 0 , v 1 , v 2 }] = { v 0 , v 1 , v 2 }, every geodetic set of D 2 must contain some vertices of U . Let g ( D 2 ) = t + 3, where T = { u 1 , u 2 , · · · , ut , v 0 , v 1 , v 2 } is a minimum geodetic set of D 2 .
We now show that S = { u 1 , u 2 , · · · , ut , v 0 , v 2 } is a geodetic set of D 1 . Let w V ( D 1 ). We show that w lies on some x y geodesic for x, y S . Since this is clearly true if w S , we may assume that w V ( D 1 ) – S . Since v 1 lies on the geodesic v 0 , v 1 , v 2 in D 1 , we need only consider the case where w U S .
Now w lies on some a b geodesic in D 2 , where a, b ∈ { u 1 , u 2 · · ·, ut }, that is, w lies on a ui uj geodesic in D 2 for some i and j with 1 ≤ i j t , where V ( P ) ⊆ U . Since there is no directed ur us path in D 1 containing any of v 0 , v 1 , v 2 for all pairs r, s with 1 ≤ r s t , it follows that P is ui uj geodesic in D 1 as well. Hence S is a geodetic set for D 1 and g ( D 1 ) ≤ t +2, implying that g ( D 1 ) < g ( D 1 ) and so g ( G ) < g + ( G ).
A. Farrugia [7] also showed that if G is any connected graph of order n ≥ 3, then h ( G ) < h + ( G ).
Theorem 2.3. For any connected graph G of order n ≥ 3, h ( G ) < h + ( G ).
Since every geodetic set is a hull set, we have h ( D ) ≤ g ( D ) for every directed graph D . Therefore we have h ( G ) ≤ g ( G ) and h + ( G ) ≤ g + ( G ). There are many classes for which h ( G ) = g ( G ) < h + ( G ) = g + ( G ).
Theorem 2.4. (1) If T is a tree of order n ≥ 2 with k end-vertices, then g ( T ) = h ( T ) = k and g + ( T ) = h + ( T ) = n .
(2) For n ≥ 3, g ( Cn ) = h ( Cn ) = 2 and g + ( Cn ) = h + ( Cn ) = n if n = 3 or n is even; otherwise g + ( Cn ) = h + ( Cn ) = n – 1.
(3) For integers r and s with 2 ≤ r s, g ( Kr,s ) = h ( Kr,s ) = 2 and g + ( Kr,s ) = h + ( Kr,s ) = r + s .
Proof . (1) Since a tree T is bipartite, g + ( T ) = h + ( T ) = n . And since every geodetic set S of T contains all the end-vertices, we have | S | ≥ k . For every vertex u V ( T ) – S ′, u lies in some v w geodesic, where S ′ is a set of all the end-vertices and v,w S ′ with | S ′| = k . Therefore, S ′ is a minimum geodetic set and g ( T ) = h ( T ) = k .
(2) Every pair of distinct vertices of the directed cycle
PPT Slide
Lager Image
is a geodetic set. So g ( Cn ) = h ( Cn ) = 2.
If n = 3, then there is an transitive orientation of C 3 and so g + ( Cn ) = h + ( Cn ) = n .
If n is even, we direct the two edges incident with vi towards vi for all even i . Then every vertex of Cn has indegree or outdegree 0. So any geodetic set contains all the vertices of Cn . Therefore, g + ( Cn ) = h + ( Cn ) = n .
If n is odd( n ≥ 5), let V ( Cn ) = { v 1 , v 2 , · · ·, v 2k+1 }. Now we direct the two edges incident with vi towards v i for all i even and have an arc ( v 1 , v 2k+1 ). Then each vertex vi (1 ≤ i ≤ 2 k ) has indegree or outdegree 0 and vertex v 2k+1 lies in v 1 v 2k geodesic. So { v 1 , v 2 , · · ·, v 2k } is a minimum geodetic set and g + ( Cn ) = h + ( Cn ) = 2 k = n – 1.
(3) There exists an orientation of Kr,s having directed Hamiltonian path. So g ( Kr,s ) = h ( Kr,s ) = 2. And since Kr,s is bipartite, g + ( Kr,s ) = h + ( Kr,s ) = r + s .
Now we focus our study on the relation g ( G ) < h + ( G ). J-T. Hung et al. [9] proved that this relation holds for every connected graph of order n ≥ 3.
Lemma 2.5. Suppose that G is a connected graph of order n ≥ 3 and T is a spanning tree of G with k leaves. Then g ( G ) ≤ k .
Proof . Let S be the set of all leaves of T and r be a leaf of T . Define an orientation D of G by (i) if uv E ( T ) and dT ( r, u ) > dT ( r, v ), then ( v, u ) ∈ E ( D ), and (ii) if uv E ( G ) \ E ( T ) and dT ( r, u ) > dT ( r, v ), then ( u, v ) ∈ E ( D ), and (iii) assign any arbitrary directions to the other edges. In D , we have that the paths from r to the other leaves in T are geodesics of D . That is, S is a geodetic set of D . By the definition, g ( G ) ≤ g ( D ) ≤ | S | = k .
Theorem 2.6. If a graph G of order n ≥ 3 has a Hamiltonian path, then 2 = h ( G ) = g ( G ) < h + ( G ). Furthermore, if n ≥ 4, then 2 = h ( G ) = g ( G ) < h + ( G ) – 1.
Proof . Since G has a Hamiltonian path, by Lemma 2.5, g ( G ) ≤ 2. Thus, 2 ≤ h ( G ) ≤ g ( G ) ≤ g ( D ) = 2. Therefore 2 = h ( G ) = g ( G ).
If n = 3 and G is connected, then G is either a complete graph or a path. It is easy to see that h + ( G ) = 3; that is, the statement of the theorem is true for n = 3. For G being a complete graph, the hull number of an acyclic tournament of order n is n . So 2 = g ( G ) < h + ( G ) = n for n ≥ 3. We assume that G is not a complete graph and the order of G is at least 4, then there exist u, v V ( G ) such that uv E ( G ).
Case 1. NG ( u ) ∩ NG ( v ) =
PPT Slide
Lager Image
.
Take x NG ( u ) and y NG ( v ). Construct an orientation D 1 of G by the following steps:
(1) if us, tx E ( G ), then ( u, s ), ( t, x ) ∈ E ( D 1 ),
(2) if ys, tv E ( G ), then ( y, s ), ( t, v ) ∈ E ( D 1 ),
and (3) assign any arbitrary directions to the other edges.
Since NG ( u ) ∩ NG ( v ) =
PPT Slide
Lager Image
, the vertices u and y are sources and the vertices x and v are sinks in D 1 . Therefore the vertices u, v, x, y must be in every hull set of D 1 . Hence h + ( G ) ≥ h ( D 1 ) ≥ 4 = h ( G ) + 2.
Case 2. NG ( u ) ∩ NG ( v ) ≠
PPT Slide
Lager Image
.
Take x NG ( u ) ∩ NG ( v ). Construct an orientation D 2 of G by the following steps:
(1) if ut, vs E ( G ), then ( u, t ), ( v, s ) ∈ E ( D 2 ),
(2) if tx E ( G ), then ( t, x ) ∈ E ( D 2 ),
and (3) assign any arbitrary directions to the other edges.
In D 2 , the vertices u and v are sources and the vertex x is a sink. Then the vertices u, v and x must be in every hull set of D 2 . Since | V ( G )| ≥ 4 and [{ u, v, x }] D2 = { u, v, x } ≠ V ( G ). We have that h + ( G ) ≥ h ( D 2 ) ≥ 4 = h ( G ) + 2.
Theorem 2.7. If G is a connected graph with at least 3 vertices, then g ( G ) < h + ( G ).
Proof . Suppose that G is a connected graph with order n ≥ 3. If G has a Hamiltonian path, then by Theorem 2.6, the statement of the theorem is true. So we assume that G has no Hamiltonian path. Let T be a spanning tree of G obtained by the depth-first search algorithm where V ( T ) = { u 1 , u 2 , · · ·, un } (the order is given by the search with u 1 as the root vertex of T ) and the leaves of T be v 1 , v 2 , · · ·, vk . By G having no Hamiltonian path, k ≥ 3, and if ui uj E ( G ) with i < j , then ui is a vertex in the path from u 1 to uj in T .
If u 1 is not a leaf in T , then by the depth-first search algorithm, v 1 , v 2 , · · ·, vk are independent in G . (If ui = va , uj = vb , i < j , and vavb E ( G ), then va is not a leaf of T .) Construct an orientation D 1 of G by ( ui , uj ) ∈ E ( D 1 ) if and only if uiuj E ( G ) and i < j . Then u 1 is a source and v 1 , v 2 , · · ·, vk are sinks in D 1 ; that is, every hull set of D 1 contains, v 1 , v 2 , · · ·, vk . Thus, h + ( G ) ≥ h ( D 1 ) ≥ k + 1. By Lemma 2.5, g ( G ) ≤ k < k + 1 ≤ h + ( G ).
If u 1 is a leaf in T , then u 1 = v 1 . There exits:
(a) If u 1 vi E ( G ) for all i = 2, 3, · · ·, k , then v 1 , v 2 , · · ·, vk are independent. We can construct an orientation D 2 of G in which v 1 , v 2 , · · ·, vk are sinks in D 2 . Then every hull set of D 2 contains v 1 , v 2 , · · ·, vk . Since [{ v 1 , v 2 , · · ·, vk }] D2 = { v 1 , v 2 , · · ·, vk }, h + ( G ) ≥ h ( D 2 ) ≥ k + 1. By Lemma 2.5, g ( G ) ≤ k < h + ( G ).
(b) If there exists j ∈ {2, 3, · · ·, k } such that u 1 vi E ( G ), then let i be a smallest number such that degT ( ui ) ≥ 3, and T ′ be a spanning tree of G with E ( T ′) = E ( T ) \ { ui-1 ui } ∪ { u 1 vi }. Then the number of leaves in T ′ is k – 1. By Lemma 2.5, g ( G ) ≤ k – 1. Let D 3 be an orientation of G defined by ( ui , uj ) ∈ E ( D 3 ) if and only if uiuj E ( G ) and i < j . In D 3 , u 1 is a source and v 2 , v 3 , · · ·, vk are sinks; that is, h + ( G ) ≥ h ( D 3 ) ≥ k .
Hence g ( G ) < h + ( G ) for G of order n ≥ 3. The theorem then follows.
The following is a direct consequence of Theorem 2.7.
Corollary 2.8. If G is a connected graph of order n ≥ 3, then h ( G ) ≤ g ( G ) < h + ( G ) ≤ g + ( G ).
BIO
Byung Kee Kim received his Ph. D from Korea University. He is now a professor of Cheongju University. His research interest focuses on graph theory and topology.
Department of Mathematics Education, Cheongju University, Cheongju, Chungbuk 360-764, Korea
e-mail: bkkim@cju.ac.kr
References
Buckley F. , Harary F. 1990 Distance in graphs Addison-Welsey Reading, MA
Chartrand G. , Fink J. F. , Zhang P. (2003) The hull number of an oriented graph Int. J. Math. Math. Sci. 36 2265 - 2275    DOI : 10.1155/S0161171203210577
Chartrand G. , Harary F. , Zhang P. (1998) Extremal problems in geodetic graph theory congress Number 130 157 - 168
Chartrand G. , Zhang P. (2000) The geodetic number of an oriented graph Europ, J. combinatorics 21 181 - 189    DOI : 10.1006/eujc.1999.0301
Everett M. G. , Seidman S. B. (1985) The hull number of a graph Discrete Math. 57 217 - 223    DOI : 10.1016/0012-365X(85)90174-8
Faghani M. , Ashrafi A. R. , Ori O. (2012) Remarks on the Wiener polarity index of some graph operations J. Appl. Math. & Informatics 30 (3-4) 353 - 364
Farrugia A. (2005) Orientable convexity, geodetic and hull numbers in graphs Discete Appl. Math. 148 256 - 262    DOI : 10.1016/j.dam.2005.03.002
Harary F. , Nieminen J. (1981) Convexity in graphs J. Differ. Geom. 16 185 - 190
Hung J-T. , Tong L-D. , Wang H-T. (2009) The hull and geodetic numbers of orientations of graphs Discrete Math. 309 2134 - 2139    DOI : 10.1016/j.disc.2008.04.034