Geodetic Number and Geo-Chromatic Number of 2-Cartesian Product of Some Graphs ()
1. Introduction
Products of structures are a fundamental construction in mathematics, for which theorems abound in set theory, category theory, universal algebra etc. Product in graphs is a natural extension of concepts of graphs involved in the product. The most famous, well studied graph product is the cartesian product. It not only extends many properties, but also carries metric space structure with it. Combining the usual vertex distance as a metric, the cartesian product is generalized to give multidimensional aspect to the underlying graphs. A special case of this was studied as 2-cartesian product by Acharya [1] [2]. These papers throw light on 2-cartesian product of some special graphs. Inspired by these, in this paper we consider finding geodetic number of 2-cartesian product of graphs and then extend them to find geochromatic number. Geodetic number primarily deals with distance convexity which is studied by many researchers [3] [4] [5], etc. The depth of convexity theory enables study of geodeticity in graphs to further heights. Another interesting concept in graphs that finds numerous applications is that of coloring. Recently these two concepts are combined to give geochromatic number, which acts as a double layered measure that covers all vertices in a graph containing all color class representations. The geochromatic number of a graph was defined by Samli et al. [6], which was further studied by Mary [7], Huilgol et al. [8]. In this paper we determine the geodetic number of 2-cartesian product of some graphs and extend them to find geochromatic number.
First of all, we list some important preliminaries.
2. Definitions and Preliminary Results
All the terms undefined here are in the sense of Buckley and Harary [9]. Here we consider a finite graph without loops and multiple edges. For any graph G the set of vertices is denoted by
and the edge set by
. The order and size of G are denoted by p and q respectively.
Let u and v be vertices of a connected graph G. A shortest
path is called a
-geodesic. The distance between two vertices u and v is defined as the length of a
geodesic in G and is denoted by
or
if G is clear from the context.
The eccentricity of vertex v of a graph G denoted by
is maximum distance from v to any other vertex of G. Diameter of G, denoted by
is the maximum eccentricity of vertices in G, and radius is the minimum such eccentricity denoted by
.
Definition 2.1. [9] A vertex v of G is a peripheral vertex if
.
Definition 2.2. [9] The set of all peripheral vertices of G is called periphery, denoted by
. That is,
.
Definition 2.3. [9] A graph G is said to be self-centered if
.
Definition 2.4. [9] If each vertex of a graph G has exactly one eccentric vertex, then G is called a unique eccentric vertex graph.
Definition 2.5. [9] The (geodesic) interval
between u and v is the set of all vertices on all shortest
paths. Given a set
, its geodetic closure
is the set of all vertices lying on some shortest path joining two vertices of S. Thus,
.
A set
is called a geodetic set in G if
; that is every vertex in G lies on some geodesic between two vertices from S. The geodetic number
of a graph G is the minimum cardinality of a geodetic set in G.
Definition 2.6. [10] A n-vertex coloring of G is an assignment of n colors 1, 2, 3, ..., n to the vertices of G. The coloring is proper if no two adjacent vertices have the same color.
Definition 2.7. [10] A set
is called chromatic set if C contains all vertices belonging to each color class. Chromatic number of G is the minimum cardinality among all chromatic sets of G, that is,
.
Definition 2.8. [6] A set
of vertices in G is said to be geochromatic set, if
is both a geodetic set and a chromatic set. The minimum cardinality of a geochromatic set of G is its geochromatic number (GCN) and is denoted by
. A geochromatic set of size
is said to be
-set.
Definition 2.9. [4] A vertex v in G is an extreme vertex if the subgraph induced by its neighborhood is complete.
Definition 2.10. [5] Let G be a graph and let
be a geodetic set of G, then S is a linear geodetic set if for any
there exists an index i,
such that
.
Definition 2.11. [5] Let G be a graph, If S is a geodetic set of G such that, for all
, for all
then S is a complete geodetic set of G.
The following results are helpful in proving our results.
Theorem 1. [11] Every geodetic set of a graph contains its extreme vertices.
Theorem 2. [5] If G is a non trivial connected graph of order p and diameter d, then
.
Theorem 3. [9] If every chromatic set of a graph G contains k vertices, then G has k vertices of degree at least
.
Theorem 4. [10] Every minimum chromatic set of a graph G contains at most
vertices.
Theorem 5. [10] If
, a complete graph on t vertices, then
is the unique chromatic set of G.
3. Geodetic Number and Geochromatic Number of 2-Cartesian Product of Some Graphs
We establish the geodetic number of graphs resulting from 2-cartesian product of two graphs. We first give some definitions and preliminary results pertaining to 2-cartesian products, geodeticity, chromaticity and geochromaticity with respect to 2-cartesian product in paths, cycles and complete bipartite graphs.
Definition 3.1. [12] The cartesian product
of graphs G and H is the graph with vertex set
in which vertices
and
are adjacent whenever
and
or
and
.
By [12] most important metric property of the cartesian product operation is written as follows
, for any two graphs G and H.
Theorem 6. [12] For any two graphs G and H,
.
Remark 1. In the cartesian product color assignment is given as follows: Whenever
, let
be a coloring of G and
be a coloring of H.A color assignment f is
, defined by
.
Theorem 7. [13] Let
be the cartesian product of connected graphs G and H and let
,
be vertices of X then,
. Moreover,
.
Theorem 8. [11] For any graphs G and H,
, then
Theorem 9. [11] Let G and H be graphs on at least two vertices with
and let
. Suppose that both G and H contain linear
minimum geodetic sets, then
.
Theorem 10. [5] Let G be a graph on at least two vertices that admits a linear minimum geodetic set and let H be a graph with
, then
.
Theorem 11. [11] Let G and H be non trivial graphs, both being non trivial graphs having complete minimum geodetic sets. Let H be a graph with
then
.
Theorem 12. [8] For the cartesian product of two paths, that is, the grid graphs, the geochromatic number is given by,
Theorem 13. [8] For the cartesian product of cycle
with path
, the geo-chromatic number is given by,
or 3.
Theorem 14. [8] For the cartesian product of cycle
with cycle
the geo-chromatic number is given by,
or 5.
Theorem 15. [8] For the cartesian product of complete graph
with path
the geochromatic number is given by,
Theorem 16. [8] For the cartesian product of complete graph
with cycle
the geochromatic number is given by,
Definition 3.2. [2] The 2-cartesian product of graphs
and
is the graph
with the vertex set
and the edge set E defined as follows:
Two vertices
and
are adjacent in G if one of the conditions is satisfied:
1)
and
,
2)
and
.
We denote this graph G by
.
It is clear that if we replace 2by 1in the definition,then we get usual cartesian product
.
Note that, if diameter of each graph
and
is less than 2, then
is a null graph.To avoid this,we consider all graphs with diameter at least 2.
Definition 3.3. [2] The grid graph
is defined as the graph with the vertex set
and egde set
.
Definition 3.4. [2] The semi tied grid graph
is a grid graph with the vertex set
and the edge set consisting of following edges:
1)Each edge of
;
2) The edges
,for every
.
In place of (2), if we consider (2)' then we get another semi tied grid graph denoted by
, where (2)': The edges
, for every
.
A graph containing all the above types of edges is called a tied graph, denoted by
.
Proposition 3.1. [2] For
,
1) If both m and n are even integers then,
.
2)If m is odd and n is even, then,
.
3) If m is even and n is odd, then,
.
4)If both m and n are odd integers, then,
.
Proposition 3.2. [2] Let
and
be path graph and cycle graph with m and n vertices respectively.
1) If n is an even integer,then
has four components which are semi tied graphs.
a) if m is even,we have 4isomorphic components
.Hence,
.
b) if m is odd,we have 2pairs of isomorphic components
and
.Hence,
.
2) If n is an odd integer,then
has two components which are semi tied graphs.
a) if m is even,we have 2isomorphic components
to give
.
b) if m is odd,we have 2non-isomorphic components
and
to give
.
Proposition 3.3. [2] Let
and
be cycle graphs with m and n vertices respectively.
1) If both m and n are even integers,then
has four isomorphic tied grid graph components are
.Hence
.
2) If m is odd and n is even,then
has two tied grid graph components
to have
.
3) If both m and n are odd integers,then
is a connected graph which is a tied grid graph.
Proposition 3.4. [2] Let
be a complete biartite graph and
be a path graph with m vertices. Then
has exactly four components.
1) If m is an even integer then
has four components two components each isomorphic to
and
and
2)If m is an odd integer then
has four components viz.,
,
,
,and
.
Proposition 3.5. [2] Let
be a complete bipartite graph and
be a cycle graph with m vertices.
1)If m is an even integer then
has four components two components each isomorphic to
and
2)If m is an odd integer then
has two components
and
.
Remark 2. By [14] [15] the geodetic number of disconnected graph is the sum of geodetic number of each component.
Theorem 17. The geodetic number of 2-cartesian product of two paths is given by,
, for
.
Proof. Let
and
be two path graphs with
and
and
and
. By Proposition 3.1 [2],
has four components with each component being a grid graph isomorphic to
with identity map as the bijection. From Theorem 11 [11], paths contain complete minimum geodetic sets, hence, we have
.
In
a geodetic set can be formed as follows depending on the values of m and n.
1) If both m and n are even integers then,
has four isomorphic
components by Proposition 3.1 [2], that is,
. As each
component is isomorphic to
, a geodetic set is of the form,
or
or
or
or
or
or
or
.
2) If m is odd and n is even, then
has two pairs of isomorphic components by Proposition 3.1 [2]. Hence,
. Here a geodetic set is of the form,
or
or
or
or
or
or
or
.
3) If m is even and n is odd, then
has two pairs of isomorphic components by Proposition 3.1 [2]. Hence,
. Here a geodetic set is of the form,
or
or
or
or
or
or
or
.
4) If both m and n are odd integers, then
has four non-isomorphic components by Proposition 3.1 [2]. Therefore,
. A geodetic
set is of the form,
or
or
or
or
or
or
or
.
By [14] [15] each component has geodetic number 2. Hence
, for
. □
Corollary 3.1. The geochromatic number of 2-cartesian product of two paths is given by,
, for
.
Proof. By Theorem 6 [12], we have
. Hence, geodetic set of each component of
is bicolorable. By the above theorem, each component has geodetic number 2. Since
has four components isomorphic to
, by Theorem 12 [8] the result follows. □
Theorem 18. The geodetic number number of 2-cartesian product of path
with cycle
is given by,
Proof. Let
be a path with m vertices and
be a cycle with n vertice. Let the vertices abd edges be labelled as
and
. Similarly, let
and
. Hence, we have
. As given in the statement, we have three cases as follows:
Case 1: Let n be an odd interger of the form, say,
and
with
.
Here we consider two subcases, depending on whether m is odd or even.
Subcase (1a): Let m be odd.
By Proposition 3.2 [2], we get two non-isomorphic components, that is,
. We see that
and
with the identity map as the bijection. As paths contain complete minimum geodetic sets and
cycles contain linear geodetic sets, by Theorem 10 [5], we have
. The geodetic set is of the
form
or
, for
. Similarly, for other component the geodetic set is of the form
or
. Hence the geodetic set is given by
or
or
or
. By [14] [15] each component has geodetic number 3. Therefore
.
Subcase (1b): Let m be even.
By Proposition 3.2 [2], we get two isomorphic components, that is,
. We have
with identity map as the bijection. Similar to the above case we get by Theorem 10 [5], we have
. The geodetic set is of the form
or
, for
. By [14] [15] each component has geodetic number 3, to give
.
Case 2: Let n be even of the form
,
and l odd.
Here we consider two subcases, depending on whether m is even or odd.
Subcase (2a): Let m be even.
By Propsition 3.2 [2], we get four isomorphic components, that is,
and we see that
with identity map as the bijection. Hence by Theorem 10 [5],
. The geodetic
set is of the form
or
for
. By [14] [15] each component has geodetic number 3. Therefore,
.
Subcase (2b): Let m be odd.
By Propsition 3.2 [2], we have 2 pairs of isomorphic components, that is,
. We see that
and
with identity map as the bijection. Hence by Theorem 3.5 [5], we have
.
The geodetic set is of the form
or
for
. By [14] [15] each component has geodetic number 3. Therefore
.
Case 3: Let n be even of the form
,
and l even.
Here we consider two subcases, depending on whether m is odd or even.
Subcase (3a): Let m be even.
By Proposition 3.2 [2], we have four isomorphic components, that is,
and we see that
with identity
map as the bijection. Similar to the above case, by Theorem 3.5 [5], we have
. The geodetic set is of the form
or
for
. By [14] [15] each component has geodetic number 2. Therefore
.
Subcase (3b): Let m be odd.
By Proposition 3.2 [2], we have 2 pairs of isomorphic components, that is,
and we see that
and
with identity map as the bijection. Similar to above cases, by Theorem 10 [5], we have
and
. The geodetic set is of the form
or
for
. By [14] [15] each component has geodetic number 2. Therefore
. □
Corollary 3.2. The geochromatic number of 2-cartesian product of path
cycle
is given by,
Proof. By Theorem 6 [12], we have
if n is odd and
if n is even. By the above theorem, each component has geodetic number 2 or 3, and
has either two or four components isomorphic to
. A geodetic set can be found using union from each component, and hence we can permute the vertices of such a geodetic set to have all color class representation, to give a geochromatic set. By Theorem 13 [8], the result follows. □
Theorem 19. For the 2-cartesian product of cycle
with cycle graph
the geodetic number is given by,
Proof. Let
be a cycle with m vertices and
be a cycle with n vertices, labelled as
and
and
and
. Then we have
. As given in the statement we have the following cases:
Case 1: Let
be odd of the form,
.
By Proposition 3.3 [2],
is a connected graph isomorphic to
, a tied grid graph. Further,
. By Theorem 14 [8], we get
and the geodetic set is of the form
, for
and
. Hence
Case 2: For
,
,
,
with
even.
By Proposition 3.3 [2] we have four isomorphic components, that is,
and
with identity map
as the bijection. By Theorem 11 [11], we have
. The geodetic sets are of the form
or
for
and
. By [14] [15] each component has geodetic number 2. Hence geodetic set of
.
Case 3: For
,
, with l even and
,
with k even.
By Proposition 3.3 [2], we get two pairs of isomorphic components, that is,
and
with identity map
as the bijection. Similar to the above case by Theorem 11 [11], we get
. The geodetic set is given by
or
for
and
. By [14] [15] each component has geodetic number 3. Hence geodetic set of
.
Case 4: For
,
with l odd and
, n with k odd.
By Proposition 3.3 [2], we get two pairs of isomorphic components, that is,
and
with identity
map as the bijection. Similar to the above case by Theorem 11 [11], we have
. The geodetic set is given by
or
. By [14] [15] each component has geodetic number 3. Hence geodetic set of
.
Case 5: For
,
and k odd, l even.
By Proposition 3.3 [2], we get four isomorphic components, that is,
and
with identity map
as the bijection. Using Theorem 11 [11], we get
. The geodetic set is given by
or
. By [14] [15] each component has geodetic number 3, hence geodetic number of
.
Case 6: For
,
and
odd.
By Proposition 3.3 [2], we get four isomorphic components, that is,
and
with identity map
as the bijection. By Theorem 14 [8] we get
. The geodetic sets are of the form
.
By [14] [15] each component has geodetic number 5. Hence
.
□
Corollary 3.3. The geochromatic number of 2-cartesian product of cycle
with cycle
is given by,
Proof. By Theorem 6 [12],
, if n is odd and
, if n is even. By the above theorem, each component has geodetic number 2, 3 or 5. A geodetic set can be found using union from each component, and hence we can permute the vertices of such a geodetic set to have all color class representation, to give a geochromatic set. By Theorem 14 [8] result follows. □
Theorem 20. The geodetic number of 2-cartesian product of complete bipartite graph
with path
is given by,
Proof. Let
be a complete bipartite graph with
and
as two partite sets. Let
.
and
contain complete minimum geodetic sets. As given in the statement we have the following cases depending on
and m.
Case 1: Let m be even.
Using Proposition 3.4 [2], we get two pairs of isomorphic components of the
form
or
with identity mapping as the bijection. We know
that each component is isomorphic to cartesian product of a complete graph and a path. Hence, we get the geodetic number to be s or t. By Theorem 11 [11],
, for
and
, for
. Hence a geodetic set is of the form
or
for
(
or t), (
or t) and
. By [14] [15] each component has geodetic number is s and t. Hence
or 4t, if
and
, if
.
Case 2: Let m be odd.
Using Proposition 3.4 [2], we have four non isomorphic components, that is,
,
,
,
with identity mapping as the
bijection and each being isomorphic to the cartesian product of a complete graph and a path. Similar to the above case, we get the geodetic number equal to s or t, in each case by [14] [15]. Hence
. □
Corollary 3.4. The geochromatic number of 2-cartesian product of complete bipartite graph
with path
is given by,
Proof. By Theorem 6 [12],
, we have
is s colorable and
is t colorabe. By the above theorem, each component has geodetic number s or t. Since
has four components isomorphic to
each of them being s and t colorable. A geodetic set can be found using union for each component and hence we can permute the vertices of such geodetic set to have all color class representation, to give a geochromatic set. By Theorem 15 [8], the result follows. □
Theorem 21. The geodetic number of 2-cartesian product of complete bipartite graph
with cycle
is given by,
Proof. Let
be a complete bipartite graph with
and
partite sets. Let
. As given in the statement, we have the following cases depending on
and m.
Case 1: Let m be even.
Using Proposition 3.5 [2], we have four components, two components each
isomorphic to
and
with identity mapping as the bijection
and each being isomorphic to cartesian product of a complete graph and a cycle.
Hence, by Theorem 11 [11] we have
and
, we get the geodetic number equal to s or t, by [14]
[15] for each component. Hence geodetic set is of the form
, for
,
. Hence
or 4s, if
and
if
.
Case 2: Let m be odd.
Using Proposition 3.5 [2], we get two components isomrphic to
,
. By Theorem 16 [8], we get
and
and a geodetic set is of the form
for (
or t), (
or t) and
. By [14] [15] each component has geodetic number is
and
. Hence
. □
Corollary 3.5. The geochromatic number of 2-cartesian product of complete bipartite graph
with cycle
is given by,
Proof. By Theorem 6 [12],
. By the above theorem, each component has geodetic number
. Since
has two or four components isomorphic to
. A geodetic set can be found using union from each component and hence we can permute the vertices of such a geodetic set to have all color class representation, to get a geochromatic set. By Theorem 16 [8] result follows. □
4. Conclusion
Here we have determined geodetic number and geochromatic number of 2-cartesian product of some special class of graphs like complete graphs, cycles and paths. This procedure can be extended to find the geodetic number and geo-chromatic number of r-cartesian products, in general for graphs.
Acknowledgements
We highly appreciate suggestions given by unknown referees that have improved overall presentation of the paper.