THE ORIENTABLE NUMBERS OF A GRAPH

Journal of Applied Mathematics & Informatics.
2014.
Sep,
32(3_4):
503-509

- Received : November 05, 2013
- Accepted : February 20, 2014
- Published : September 28, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

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.
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
] =
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
id_{D}
(
v
) = 0
od_{D}
(
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.
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,
Similarily, the lower orientable hull number
h
^{–}
(
G
) and the upper orientable hull number
h
^{+}
(
G
) are defined. So we have
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}
, · · · ,
v_{n}
. We first orient
G
transitively (that is, (
v_{i}
,
v_{j}
) ∈
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}
v_{n}
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}
, · · · ,
u_{t}
,
v
_{0}
,
v
_{1}
,
v
_{2}
} is a minimum geodetic set of
D
_{2}
.
We now show that
S
= {
u
_{1}
,
u
_{2}
, · · · ,
u_{t}
,
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}
· · ·,
u_{t}
}, that is,
w
lies on a
u_{i}
–
u_{j}
geodesic in
D
_{2}
for some
i
and
j
with 1 ≤
i
≠
j
≤
t
, where
V
(
P
) ⊆
U
. Since there is no directed
u_{r}
–
u_{s}
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
u_{i}
–
u_{j}
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
^{–}
(
C_{n}
) =
h
^{–}
(
C_{n}
) = 2
and g
^{+}
(
C_{n}
) =
h
^{+}
(
C_{n}
) =
n if n
= 3
or n is even; otherwise g
^{+}
(
C_{n}
) =
h
^{+}
(
C_{n}
) =
n
– 1.
(3) For integers r and s with
2 ≤
r
≤
s, g
^{–}
(
K_{r,s}
) =
h
^{–}
(
K_{r,s}
) = 2
and
g
^{+}
(
K_{r,s}
) =
h
^{+}
(
K_{r,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
is a geodetic set. So
g
^{–}
(
C_{n}
) =
h
^{–}
(
C_{n}
) = 2.
If
n
= 3, then there is an transitive orientation of
C
_{3}
and so
g
^{+}
(
C_{n}
) =
h
^{+}
(
C_{n}
) =
n
.
If
n
is even, we direct the two edges incident with
v_{i}
towards
v_{i}
for all even
i
. Then every vertex of
C_{n}
has indegree or outdegree 0. So any geodetic set contains all the vertices of
C_{n}
. Therefore,
g
^{+}
(
C_{n}
) =
h
^{+}
(
C_{n}
) =
n
.
If
n
is odd(
n
≥ 5), let
V
(
C_{n}
) = {
v
_{1}
,
v
_{2}
, · · ·,
v
_{2k+1}
}. Now we direct the two edges incident with
v_{i}
towards
v
_{i}
for all
i
even and have an arc (
v
_{1}
,
v
_{2k+1}
). Then each vertex
v_{i}
(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
^{+}
(
C_{n}
) =
h
^{+}
(
C_{n}
) = 2
k
=
n
– 1.
(3) There exists an orientation of
K_{r,s}
having directed Hamiltonian path. So
g
^{–}
(
K_{r,s}
) =
h
^{–}
(
K_{r,s}
) = 2. And since
K_{r,s}
is bipartite,
g
^{+}
(
K_{r,s}
) =
h
^{+}
(
K_{r,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
d_{T}
(
r, u
) >
d_{T}
(
r, v
), then (
v, u
) ∈
E
(
D
), and (ii) if
uv
∈
E
(
G
) \
E
(
T
) and
d_{T}
(
r, u
) >
d_{T}
(
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.
N_{G}
(
u
) ∩
N_{G}
(
v
) =
.
Take
x
∈
N_{G}
(
u
) and
y
∈
N_{G}
(
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
N_{G}
(
u
) ∩
N_{G}
(
_{v}
) =
, 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.
N_{G}
(
u
) ∩
N_{G}
(
v
) ≠
.
Take
x
∈
N_{G}
(
u
) ∩
N_{G}
(
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}
, · · ·,
u_{n}
} (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}
, · · ·,
v_{k}
. By
G
having no Hamiltonian path,
k
≥ 3, and if
u_{i}
u_{j}
∈
E
(
G
) with
i
<
j
, then
u_{i}
is a vertex in the path from
u
_{1}
to
u_{j}
in
T
.
If
u
_{1}
is not a leaf in
T
, then by the depth-first search algorithm,
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
are independent in
G
. (If
u_{i}
=
v_{a}
,
u_{j}
=
v_{b}
,
i
<
j
, and
v_{a}v_{b}
∈
E
(
G
), then
v_{a}
is not a leaf of
T
.) Construct an orientation
D
_{1}
of
G
by (
u_{i}
,
u_{j}
) ∈
E
(
D
_{1}
) if and only if
u_{i}u_{j}
∈
E
(
G
) and
i
<
j
. Then
u
_{1}
is a source and
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
are sinks in
D
_{1}
; that is, every hull set of
D
_{1}
contains,
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
. 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}
v_{i}
∉
E
(
G
) for all
i
= 2, 3, · · ·,
k
, then
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
are independent. We can construct an orientation
D
_{2}
of
G
in which
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
are sinks in
D
_{2}
. Then every hull set of
D
_{2}
contains
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
. Since [{
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
}]
_{D2}
= {
v
_{1}
,
v
_{2}
, · · ·,
v_{k}
},
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}
v_{i}
∈
E
(
G
), then let
i
be a smallest number such that
deg_{T}
(
u_{i}
) ≥ 3, and
T
′ be a spanning tree of
G
with
E
(
T
′) =
E
(
T
) \ {
u_{i-1}
u_{i}
} ∪ {
u
_{1}
v_{i}
}. 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 (
u_{i}
,
u_{j}
) ∈
E
(
D
_{3}
) if and only if
u_{i}u_{j}
∈
E
(
G
) and
i
<
j
. In
D
_{3}
,
u
_{1}
is a source and
v
_{2}
,
v
_{3}
, · · ·,
v_{k}
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
).
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

1. Introduction

The distance
PPT Slide

Lager Image

2. The relation h–(G) ≤ g–(G) < h+(G) ≤ g+(G)

In general, for a connected graph
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

BIO

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**

Citing 'THE ORIENTABLE NUMBERS OF A GRAPH
'

@article{ E1MCA9_2014_v32n3_4_503}
,title={THE ORIENTABLE NUMBERS OF A GRAPH}
,volume={3_4}
, url={http://dx.doi.org/10.14317/jami.2014.503}, DOI={10.14317/jami.2014.503}
, number= {3_4}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={KIM, BYUNG KEE}
, year={2014}
, month={Sep}