Labelling matrices and index matrices of a graph structure
The concept of graph structure was introduced by E. Sampathkumar in 'Generalised Graph Structures', Bull. Kerala Math. Assoc., Vol 3, No.2, Dec 2006, 65-123. Based on the works of Brouwer, Doob and Stewart, R.H. Jeurissen has ('The Incidence Matrix and Labelings of a Graph', J....
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2013
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/152307 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Labelling matrices and index matrices of a graph structure / T. Dinesh, T. V. Ramakrishnan // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 1. — С. 42–60. — Бібліогр.: 12 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859744241410899968 |
|---|---|
| author | Dinesh, T. Ramakrishnan, T.V. |
| author_facet | Dinesh, T. Ramakrishnan, T.V. |
| citation_txt | Labelling matrices and index matrices of a graph structure / T. Dinesh, T. V. Ramakrishnan // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 1. — С. 42–60. — Бібліогр.: 12 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | The concept of graph structure was introduced by E. Sampathkumar in 'Generalised Graph Structures', Bull. Kerala Math. Assoc., Vol 3, No.2, Dec 2006, 65-123. Based on the works of Brouwer, Doob and Stewart, R.H. Jeurissen has ('The Incidence Matrix and Labelings of a Graph', J. Combin. Theory, Ser. B30 (1981), 290-301) proved that the collection of all admissible index vectors and the collection of all labellings for 0 form free F-modules (F is a commutative ring). We have obtained similar results on graph structures in a previous paper. In the present paper, we introduce labelling matrices and index matrices of graph structures and prove that the collection of all admissible index matrices and the collection of all labelling matrices for 0 form free F-modules. We also find their ranks in various cases of bipartition and char F (equal to 2 and not equal to 2).
|
| first_indexed | 2025-12-01T20:42:24Z |
| format | Article |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 16 (2013). Number 1. pp. 42 – 60
© Journal “Algebra and Discrete Mathematics”
Labelling matrices and index matrices
of a graph structure
T. Dinesh and T. V. Ramakrishnan
Communicated by D. Simson
Abstract. The concept of graph structure was introduced by
E. Sampathkumar in ’Generalised Graph Structures’, Bull. Kerala
Math. Assoc., Vol 3, No.2, Dec 2006, 65-123. Based on the works
of Brouwer, Doob and Stewart, R.H. Jeurissen has (’The Incidence
Matrix and Labelings of a Graph’, J. Combin. Theory, Ser. B30
(1981), 290-301) proved that the collection of all admissible index
vectors and the collection of all labellings for 0 form free F -modules
(F is a commutative ring). We have obtained similar results on graph
structures in a previous paper. In the present paper, we introduce
labelling matrices and index matrices of graph structures and prove
that the collection of all admissible index matrices and the collection
of all labelling matrices for 0 form free F -modules. We also find
their ranks in various cases of bipartition and char F (equal to 2
and not equal to 2).
Introduction
E. Sampathkumar introduced the concept of graph structure in [9].
It is in particular, a generalisation of the notions like graphs [5], signed
graphs [2], [11], [12] and edge-coloured graphs [6] with the colourings.
He defined a graph structure G as G = (V, R1, R2, ...Rk) where V is a
non-empty set and R1, R2, ..., Rk are relations on V which are mutually
disjoint such that each Ri, i = 1, 2, ..., k is symmetric and irreflexive.
2010 MSC: 05C07,05C78.
Key words and phrases: Graph structure, Ri-labelling, Ri-index vector, admis-
sible Ri-index vector, labelling matrix, index matrix, admissible index matrix..
T. Dinesh, T. V. Ramakrishnan 43
R.H. Jeurissen [8], based on the works of Brouwer [1], Doob [4] and
Stewart [10], has proved some results using incidence matrices of graphs.
He has defined index vectors and labelings and also admissible index
vectors. He has proved that if F is a commutative ring and G a graph,
the collection of all admissible index vectors and the collection of all
labellings for 0 are free F -modules. He has also found out the ranks of
these modules in various cases, namely, G is bipartite, non-bipartite, char
F = 2, char F 6= 2 etc.
We have introduced similar concepts in graph structures in [3]. Instead
of index vectors and labellings, we have introduced Ri-index vectors and Ri-
labellings there and proved some results. Here we are introducing labelling
matrices and index matrices of a graph structure. We are also proving
that the collection of all admissible index matrices and the collection of
all labelling matrices for 0 form free F -modules. We are also finding their
ranks in various cases, namely, completely bipartite, not Ri-bipartite for
some i s, char F = 2, char F 6= 2 etc.
1. Preliminaries
We first go through some concepts introduced in [9].
Definition 1 ([9]). In a graph structure G = (V, R1, R2, ..., Rk), if (u, v) ∈
Ri, (u, v) is an Ri-edge.
Definition 2 ([9]). An Ri-path between two vertices u and v is an
alternating sequence of vertices and edges consisting only of Ri-edges.
Definition 3 ([9]). A set S of vertices in a graph structure
G = (V, R1, R2, ..., Rk) is Ri-connected for any given i if any two vertices
in S are connected by an Ri-path.
Now we recall the concept of Ri-distance [3].
Definition 4 ([3]). The minimum number of Ri-edges from a vertex u
to a vertex v in any Ri-path of a graph structure G = (V, R1, R2, ..., Rk)
is called the Ri-distance from u to v. It is the number of Ri-edges from a
vertex u to a vertex v in an Ri-tree.
The incidence matrix of a graph structure is defined as follows in [9].
Definition 5 ([9]). The incidence matrix B of a graph structure
G = (V, R1, R2, ..., Rk) is a k × p matrix b = (bij) where bij is the number
of Ri-edges incident to the vertex vj .
44 Labelling matrices of a graph structure
We have defined the Ri-incidence matrix of a graph structure in [3]
similar to the incidence matrix of a graph as follows.
Definition 6 ([3]). Let G = (V, R1, R2, ..., Rk) be a graph structure. The
Ri-incidence matrix of G is defined as IRi
= (bij), where brs = 1 if vr is
incident with an Ri-edge es and 0 otherwise.
First we select a spanning Ri-tree and label the Ri-edges inside and
outside the spanning Ri-tree as in [3]. We recall the procedure.
Let G be a finite Ri-connected graph structure on p vertices with
qi number of Ri- edges, i = 1, 2, ..., k. Choose a spanning Ri-tree Ti as
follows.
Let v0 be the root. Number the vertices as v1, v2, ... successively. First
those at Ri-distance 1 from v0, then those at Ri-distance 2 and so on
(Those at same Ri-distance are numbered arbitrarily). Label the Ri-edge
(vr, vs) with r < s in the spanning Ri-tree Ti as es
i . Number the Ri-edges
outside the spanning Ri-tree Ti as e
pi
i , e
pi+1
i , ..., e
qi
i .
Then the Ti-part of the Ri-incidence matrix will be of the form
v0
v1
v2
.
.
.
.
.
.
.
.
vp−1
1 . . . 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 . . . 1 0 0 0 0 0
0 . 0 1 0 0 0 0 1 . . . 1
0 . 0 0 . 0 1 0 0 0 0
0 . 0 0 . 0 0 . 0
0 0 0 0 1 0 . 0 0 . 0
0 0 0 0 0 0 0 0 0 1 0 . 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Consider a vertex vs and let vs, vk1
, vk2
, ..., vkr
, v0 be the unique Ri-path
in Ti from vs to v0. Denote it by cr
i . Then cr
i − ck1
i + ck2
i − ... + (−1)sct
i =
[(−1)t00...0]′.
For each ITi
, there exists an upper triangular p − 1 × p − 1 matrix Di
with elements 0, ±1 and an all 1-diagonal such that
ITi
Di =
1 ±1 ±1 . . . ±1
1 0 0 0 0 0 0
0 1 0
0 . 0
0 . 0
0 . 0
0 1 0
0 0 0 0 0 0 1
T. Dinesh, T. V. Ramakrishnan 45
The top row has +1 or -1 in jth position depending on whether vj is at
odd or even Ri-distance from v0.
Consider a column of Bi, the part of IRi
corresponding to the Ri-edges
outside Ti. Suppose its 1’s are in jth and kth rows with j < k. Subtracting
jth and kth columns of ITi
Di from it (if j = 0, only k), we get
0
.
.
.
0
if Ri-distance in Ti from vj to v0 is odd and that from vk to v0 is
even or if Ri - distance in Ti from vj to v0 is even and that from vk
to v0 is odd.
2
0
.
.
.
0
if vj and vk are at even Ri-distance from v0
−2
0
.
.
.
0
if vj and vk are at odd Ri-distance from v0.
Let Ei be (0, −1) matrix with one or two -1s in each column.
(ITi
Di|Bi)
[
I Ei
0 I
]
gives
1 ±1 ±1 . . . ±1 0 . . 0 2 . . 2 −2 . . −2
1 0 0 . . . 0 0 . . 0 0 . . 0 0 . . 0
0 1 0 . . . 0 0 . . 0 0 . . 0 0 . . 0
0 0 1 . . . 0 0 . . 0 0 . . 0 0 . . 0
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . 0 0 . . 0 0 . . 0 0 . . 0
0 0 0 . . . 1 0 . . 0 0 . . 0 0 . . 0
after renumbering Ri-edges outside Ti.
The column operations on the Ri-incidence matrices will give the
incidence matrix of the graph structure in the form
(IGD|B)
[
I E
Θ I
]
=
I1 Θ . . . Θ
Θ I2 Θ . . Θ
. Θ . .
. . . .
. . . Θ
Θ Θ . . Θ Ik
46 Labelling matrices of a graph structure
where
IG =
IT1
|B1 Θ . . . Θ
Θ IT2
|B2 Θ . . Θ
. Θ . .
. . . .
. . . Θ
Θ Θ . . Θ ITk
|Bk
,
D =
D1 Θ . . . Θ
Θ D2 Θ . . Θ
. Θ . .
. . . .
. . . Θ
Θ Θ . . Θ Dk
, E =
E1 Θ . . . Θ
Θ E2 Θ . . Θ
. Θ . .
. . . .
. . . Θ
Θ Θ . . Θ Ek
and each Ii has the form of
(ITi
Di|Bi)
[
I Ei
0 I
]
.
2. Labelling matrix and index matrix
We first recall the concepts of Ri-labelling and Ri-index vector intro-
duced in [3].
Definition 7 ([3]). Let F be an abelian group or a ring and
G = (V, R1, R2, ..., Rk) be a graph structure with vertices v0, v1, ..., vp−1
and qi number of Ri-edges. A mapping from V to F is an Ri-index vector
and a mapping from Ri to F is an Ri-labelling.
Definition 8 ([3]). An Ri-labelling xi is an Ri-labelling for the Ri-index
vector ri if for each j, ri(vj) =
∑
er∈E
j
i
xi(er), where E
j
i is the set of all
Ri-edges incident with vj .
Definition 9 ([3]). Ri-index vectors for which an Ri-labelling exists are
called admissible Ri-index vectors.
Now we introduce the concepts of labelling matrix and index matrix
of a graph structure.
Definition 10. Let F be an abelian group or a ring. Let ri be an Ri-index
vector and xi be an Ri-labelling for i = 1, 2, ..., k. Then
T. Dinesh, T. V. Ramakrishnan 47
a) r =
r1 0 . . . 0
0 r2 0 . . 0
. 0 . .
. . . .
. . . .
0 . . . 0 rk
is defined to be an index matrix for G
b) x =
x1 0 . . . 0
0 x2 0 . . 0
. 0 . .
. . . .
. . . .
0 . . . 0 xk
is defined to be a labelling matrix for G.
Definition 11. The map
x :
R1
R2
.
.
.
Rk
→ F k
is a labelling for r : V k → F k if
∑
m∈Es
xi(m) = ri(xs) for s = 0, 1, 2, ..., p −
1; i = 1, 2, ..., k.
Now we prove a necessary and sufficient condition for x to be a labelling
matrix for r. For that first we recall the following lemma of [3].
Lemma 1 ([3]). Let G = (V, R1, R2, ..., Rk) be a graph structure. xi is
an Ri-labelling for Ri-index vector ri iff IRi
xi = ri.
Now we move on to prove the condition for x to be a labelling matrix
for r.
Lemma 2. Let G = (V, R1, R2, ..., Rk) be a graph structure. x is a
labelling for r iff IGx = r where
IG =
IR1
0 . . . 0
0 IR2
0 . . 0
. 0 . .
. . . .
. . . 0
0 0 . . 0 IRk
.
48 Labelling matrices of a graph structure
Proof. Let x be a labelling for r. Then by Lemma 2,
IGx =
IR1
0 . . . 0
0 IR2
0 . . 0
. 0 . .
. . . .
. . . 0
0 0 . . 0 IRk
x1 0 . . . 0
0 x2 0 . . 0
. 0 . .
. . . .
. . . 0
0 0 . . 0 xk
=
IR1
x1 0 . . . 0
0 IR2
x2 0 . . 0
. 0 . .
. . . .
. . . 0
0 0 . . 0 IRk
xk
=
r1 0 . . . 0
0 r2 0 . . 0
. 0 . .
. . . .
. . . 0
0 0 . . 0 rk
= r.
Conversely, let IGx = r. Then IRi
xi = ri for i = 1, 2, ..., k. So xi is a
labelling for ri, i = 1, 2, ..., k. ie., x is a labelling for r.
Definition 12. Let G = (V, R1, R2, ..., Rk) be a graph structure. If ri is
an admissible Ri-index vector for i = 1, 2, ..., k, then
r =
r1 0 . . . 0
0 r2 0 . . 0
. 0 . .
. . . .
. . . 0
0 0 . . 0 rk
is called an admissible index matrix for G.
Now we recall the definition of complete bipartition given in [9].
Definition 13 ([9]). A graph structure G is completely bipartite if for
each i, 1 ≤ i ≤ k, G is Ri-bipartite (with same sets of bipartition).
Now we go through some of the results proved in [3].
Theorem 1 ([3]). If F is an abelian group and v1, v2, ..., vp are vertices
of an Ri-bipartite graph structure G, then ri is an admissible Ri-index
vector iff
s
∑
j=1
ri(vj) =
p
∑
j=s+1
ri(vj) where S = {v1, v2, ..., vs} and
U = {vs+1, vs+2, ..., vp} are the sets of Ri-bipartition.
T. Dinesh, T. V. Ramakrishnan 49
Theorem 2 ([3]). If F is an abelian group and v1, v2, ..., vp are the vertices
of a non-Ri-bipartite graph structure G, then ri is an admissible Ri-index
vector iff
p
∑
j=1
ri(vj) = 2fi, for some fi ∈ F .
We now prove certain preliminary results.
Theorem 3. Let G = (V, R1, R2, ..., Rk) be a complete bipartite graph
structure. If F is an abelian group and v1, v2, ..., vp are vertices of G,
then r is an admissible index matrix iff
si
∑
j=1
ri(vj) =
p
∑
j=si+1
ri(vj), for
i = 1, 2, ..., k where S = {v1, v2, ..., vsi
} and U = {vsi+1, vsi+2, ..., vp} are
sets of bipartition.
Proof. Let r be admissible. Then ri is an admissible Ri-index vector for
i = 1, 2, ..., k. G is Ri-bipartite for i = 1, 2, ..., k. Therefore by Theorem 1,
si
∑
j=1
ri(vj) =
p
∑
j=si+1
ri(vj) =
p
∑
j=si+1
ri(vj)
for i = 1, 2, ..., k.
Conversely, let
si
∑
j=1
ri(vj) =
p
∑
j=si+1
ri(vj) =
p
∑
j=si+1
ri(vj)
for i = 1, 2, ..., k.
Then by Theorem 1, ri is an Ri-admissible index vector for i = 1, 2, ..., k.
So r is admissible.
Theorem 4. Let G = (V, R1, R2, ..., Rk) be a graph structure. If F is
an abelian group and v1, v2, ..., vp are the vertices of a graph structure
G which is not Ri-bipartite for i = 1, 2, ..., k, then r is admissible iff
p
∑
j=1
ri(vj) = 2fi for some fi ∈ F, i = 1, 2, ..., k.
Proof. Let r be admissible. Then ri is an admissible Ri-index vector, i =
1, 2, ..., k. G is not Ri-bipartite for i = 1, 2, ..., k. Therefore by Theorem 2,
p
∑
j=1
ri(vj) = 2fi for some fi ∈ F, i = 1, 2, ..., k.
50 Labelling matrices of a graph structure
Conversely, let
p
∑
j=1
ri(vj) = 2fi for some fi ∈ F, i = 1, 2, ..., k. Then by
Theorem 2, ri is an admissible Ri-index vector for i = 1, 2, ..., k. Therefore
r is admissible.
Now we move on to prove that the collection of all admissible index
matrices for a graph structure form a free F -module and find its rank.
Theorem 5. Let G = (V, R1, R2, ..., Rk) be a graph structure. If F is an
integral domain, the admissible index matrices for G form a free F -module.
Its rank is
(i) k(p − 1) if G is completely bipartite or char F = 2.
(ii) kp if G is not Ri-bipartite for i = 1, 2, ..., k and char F 6= 2.
(iii) kp if G is not Ri-bipartite except for i = i1, i2, ..., ir, char F 6= 2
and 2 is invertible.
(iv) kp − r if G is not Ri-bipartite except for i = i1, i2, ..., ir, char F 6= 2
and 2 is not invertible.
Proof. Index matrices of G belong to F kp×k. Let A = set of all admissible
index matrices. It is a subset of F kp×k.
Let r, s ∈ A. Then ri, si are admissible Ri-index vectors for i = 1, 2, ..., k.
Therefore there exists Ri-labellings xri
, xsi
, for ri and si for i = 1, 2, ..., k,
and we have
r − s =
r1 0 0 . . 0
0 r2 0 . . 0
0 0 . .
. . . .
. . . 0
0 0 . . 0 rk
−
s1 0 0 . . 0
0 s2 0 . . 0
0 0 . .
. . . .
. . . 0
0 0 . . 0 sk
=
r1 − s1 0 0 . . 0
0 r2 − s2 0 . . 0
0 0 . .
. . . .
. . . 0
0 0 . . 0 rk − sk
.
IG(xr − xs) =
IR1
0 0 . . 0
0 IR2
0 . . 0
0 0 . .
. . . .
. . . 0
0 0 . . 0 IRk
T. Dinesh, T. V. Ramakrishnan 51
{
xr1
0 0 . . 0
0 xr2
0 . . 0
0 0 . .
. . . .
. . . 0
0 0 . . 0 xrk
−
xs1
0 0 . . 0
0 xs2
0 . . 0
0 0 . .
. . . .
. . . 0
0 0 . . 0 xsk
}
=
r1 − s1 0 0 . . 0
0 r2 − s2 0 . . 0
0 0 . .
. . . .
. . . 0
0 0 . . 0 rk − sk
,
that is, xr − xs is a labelling for r − s since xri
− xsi
is a labelling for
ri − si for i = 1, 2, ..., k. So r − s ∈ A.
Let f ∈ F, r ∈ A. Then ri is Ri-admissible for i = 1, 2, ..., k. There
exists an Ri-labelling xi for ri, i = 1, 2, ..., k. fxi is a labelling for fri, i =
1, 2, .., k. So fx is a labelling for fr and hence fr ∈ A. Therefore A is an
F -module and it is a submodule of F kp×k.
Case 1: G is completely bipartite
r is admissible iff
s
∑
j=1
ri(vj) =
p
∑
j=s+1
ri(vj) for i = 1, 2, ..., k by Theo-
rem 3.
ri(vp) = ri(v1) + ... + ri(vs) − ri(vs+1) − ... − ri(vp−1).
r =
r1(v1) 0 . . . 0
r1(v2) 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
r1(vp) 0 . . . .
0 r2(v1) . . . .
. . . . . 0
. . . . . .
. . . . . .
. r2(vp) . . . .
. 0 . . . .
. . . . . .
. . . . . .
. . . . . 0
. . . . . rk(v1)
. . . . . .
. . . . . .
. . . . . .
0 0 . . 0 rk(vp)
=
r1(v1) 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
0 . . . . .
r1(v1) . . . . .
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
52 Labelling matrices of a graph structure
+
0 0 . . . 0
r1(v2) 0 . . . 0
. . . . . .
. . . . . .
0 . . . . .
r1(v2) . . . . .
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
+ ... +
0 0 . . . 0
0 0 . . . 0
. . . . . .
0 . . . . .
r1(vp−1) . . . . .
−r1(vp−1) . . . . .
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
+...+
0 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . 0
. . . . . rk(v1)
. . . . . 0
. . . . . .
. . . . . .
. . . . . 0
0 0 . . 0 −rk(v1)
+...+
0 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . 0
. . . . . rk(vp−1)
0 0 . . 0 −rk(vp−1)
Denote the above k(p − 1) matrices by
r11, r12, ..., r1(p−1), ..., rk1, ..., rk(p−1).
Let f11, ..., fk(p−1) be elements of F and let f11r11 + ...+fk(p−1)rk(p−1) = 0.
Then f11r11 = ... = fk(p−1)rk(p−1) = 0. Therefore f11 = f12 = ... =
fk(p−1) = 0 and so r11, r12, ..., rk(p−1) are linearly independent. Therefore
A is a free F -module of rank k(p − 1).
Case 2: char F = 2
The case when G is completely bipartite has already been discussed.
So it is enough if we consider G to be not completely bipartite.
Two subcases arise.
Subcase 1: G is not Ri-bipartite for i = 1, 2, ..., k.
T. Dinesh, T. V. Ramakrishnan 53
By theorem 4, r is admissible iff
p
∑
j=1
ri(vj) = 2fi for some fi ∈ F, i =
1, 2, ..., k. Since char F = 2,
p
∑
j=1
ri(vj) = 0, i = 1, 2, ..., k. Therefore
ri(vp) = −ri(v1) − ri(v2) − ... − ri(vp−1), i = 1, 2, ..., k. So we can write
r =
r1(v1) 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
0 . . . . .
−r1(v1) . . . . .
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
+
0 0 . . . 0
r1(v2) 0 . . . 0
0 . . . . .
. . . . . .
0 . . . . .
−r1(v2) . . . . .
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
+ ...
+
0 0 . . . 0
. 0 . . . 0
. . . . . .
0 . . . . .
r1(vp−1) . . . . .
−r1(vp−1) . . . . .
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
+ ... +
0 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . rk(v1)
. . . . . 0
. . . . . .
. . . . . .
. . . . . 0
0 0 . . 0 −rk(v1)
+ ...
+
0 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . 0
. . . . . rk(vp−1)
0 0 . . 0 −rk(vp−1)
Let these elements be denoted by r11, r12, ..., rk1, ..., rk(p−1) and let
f11, f12, ..., f1(p−1), ..., fk1, ..., fk(p−1) ∈ F .
54 Labelling matrices of a graph structure
If
f11r11 +f12r12 + ...+f1(p−1)r1(p−1) + ...+fk1rk1 + ...+fk(p−1)rk(p−1) = 0,
then f11 = f12 = ... = f1(p−1) = ... = fk1 = ... = fk(p−1) = 0 and hence
r11, r12, ..., rk1, ..., rk(p−1) are linearly independent. Therefore A is a free
F -module with rank k(p − 1).
Subcase 2: G is Ri-bipartite for i = i1, i2, ..., ir; i1, i2, ..., ir ∈
{1, 2, ..., k}, 1 < r < k. For i = i1, i2, ..., ir, ri is admissible iff
s
∑
j=1
ri(vj) =
p
∑
j=s+1
ri(vj)
by Theorem 1, that is,
ri(vp) = ri(v1) + ri(v2) + ... + ri(vs) − ri(vs+1) − ... − ri(vp−1)
for i = i1, i2, ..., ir. For i 6= i1, i2, ..., ir, ri is admissible iff
p
∑
j=1
ri(vj) = 2fi = 0
by Theorem 2, that is, for i 6= i1, i2, ..., ir, ri(vp) = −ri(v1) − ri(v2) − ... −
ri(vp−1). Therefore we can write r as a linear combination of k(p − 1)
matrices of which kr matrices have the form
0 0 . 0 . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . 0 . .
. . . ri(vj) . .
. . . 0 . .
. . . . . .
. . . . . .
. . . 0 . .
. . . ±ri(vj) . .
. . . 0 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . 0 . 0
T. Dinesh, T. V. Ramakrishnan 55
and the remaining have the form
0 0 . 0 . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . 0 . .
. . . ri(vj) . .
. . . 0 . .
. . . . . .
. . . . . .
. . . . . .
. . . 0 . .
. . . −ri(vj) . .
. . . 0 . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . 0 . 0
Clearly they are linearly independent. Therefore A is a free F -module of
rank k(p − 1).
Case 3: G is not Ri-bipartite for i = 1, 2, ..., k and char F 6= 2
Subcase 1: G is not Ri-bipartite for i = 1, 2, ..., k and char
F 6= 2
a) 2 is invertible
p
∑
j=1
ri(vj) = fi = (2.2−1fi) = 2(2−1fi)
for some fi ∈ F, i = 1, 2, ..., k, i.e.,
p
∑
j=1
ri(vj) = 2f ′
i , f ′
i = 2−1fi ∈ F for
i = 1, 2, ..., k. Therefore ri is Ri-admissible for i = 1, 2, ..., k by Theorem 2.
So r is admissible. Hence rank of A is rank of F kp×k = kp.
b) 2 is not invertible
Consider
56 Labelling matrices of a graph structure
s11 =
2 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
, s12 =
0 0 . . . 0
2 0 . . . 0
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
, ...,
s1p =
0 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
0 . . . . .
2 . . . . .
0 . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
, ..., sk1 =
0 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . 0
. . . . . 2
. . . . . 0
. . . . . .
. . . . . .
. . . . . .
0 0 . . . 0
, ...,
skp =
0 0 . . . 0
0 0 . . . 0
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . 0
0 0 . . . 2
Each sij is admissible by Theorem 2. Also sij ∈ A, i = 1, 2, ..., k; j =
1, 2, ..., p. Let f11, f12, ..., f1p, ..., fk1, ..., fkp ∈ F and f11s11 + f12s12 + ... +
fkpskp = 0. Then f11 = f12 = ... = fkp = 0 since char F 6= 2. Therefore
T. Dinesh, T. V. Ramakrishnan 57
s11, s12, ..., skp are linearly independent and hence A is a free F -module
with rank equal to the rank of F kp×k = kp.
Subcase 2: G is Ri-bipartite for i = i1, i2, ..., ir, 1 < r < k
and not Ri-bipartite for i = ir+1, ir+2, ..., ik where i1, i2, ..., ik ∈
{1, 2, ..., k}
a) 2 is invertible
Then
p
∑
j=1
ri(vj) = fi = 2f ′
i where f ′
i = 2−1fi ∈ F .
So ri is an admissible Ri-index vector for i = 1, 2, ..., k and hence r
is admissible by Theorem 2. Therefore rank of A is equal to rank of
F kp×k = kp.
b) 2 is not invertible
As in subcase 1 b, define s11, ..., skp. Then sij ∈ A, i = 1, 2, ..., k; j =
1, 2, ..., p. But for i = i1, i2, ..., ir, sip = si1 + si2 + ... + sis − si(s+1) − ... −
si(p−1). Therefore rank of A is equal to rank of F kp×k − r = kp − r.
Now we prove that the collection of all labelling matrices for 0 form
a free F -module and find its rank. For that, first we recall a theorem
from [3].
Theorem 6 ([3]). Let G = (V, R1, R2, ..., Rk) be a graph structure. If F
is an integral domain, the Ri-labelling of G for the Ri-index vector 0 form
a free F -module. Its rank is qi − p + 1 if G is Ri-bipartite or char F = 2
and qi − p if G is not Ri-bipartite and char F 6= 2.
Theorem 7. Let G = (V, R1, R2, ..., Rk) be a graph structure. If F is an
integral domain, the labellings of G for the index matrix 0 form a free
F -module. Its rank is
(i) q1 +q2 + ...+qk −k(p−1) if G is completely bipartite or char F = 2,
(ii) q1 + q2 + ... + qk − kp if G is not Ri-bipartite for i = 1, 2, ..., k and
char F 6= 2,
(iii) q1 + q2 + ... + qk − kp + r if G is Ri-bipartite for i = i1, i2, ..., ir and
char F 6= 2.
Proof. Define φ : F (q1+q2+...+qk)×k → {IGx} as φ(x) = IGx. Let x, y ∈
F (q1+q2+...+qk)×k.
φ(x + y) = IG(x + y) = IGx + IGy = φ(x) + φ(y),
For f ∈ F, x ∈ F (q1+q2+...+qk)×k, φ(fx) = IG(fx) = f(IGx) = fφ(x).
Therefore φ is a homomorphism. It is onto also. Let
K = {x ∈ F (q1+q2+...+qk)×k : IGx = 0}. It is the kernel of φ. Clearly it is
58 Labelling matrices of a graph structure
a submodule of F (q1+q2+...+qk)×k. Hence K is an F -module.
r is admissible iff IGx = r by Lemma 2. ie., iff (IGC)(C−1x) = r. So 0 is
admissible iff (IGC)(C−1x) = 0. ie., iff (IGC)y = 0 where y = C−1x.
Therefore a general solution for y pre-multiplied by C is a labelling for 0.
A general solution for y for r = 0 has the form
S =
Θ A1 0 . . . 0
Θ 0 A2 0 . . . 0
. . . .
. . . .
. . . .
Θ . . . . . . Ak
where Θ is a zero matrix of suitable order,
A1 =
[
αp . . . αs1
. . . αt1
. . . αq1
]
,
..., Ak =
[
αp . . . αsk
. . . αtk
. . . αqk
.
]
Also
2(αti+1 + αti+2 + ... + αsi+1 − αsi
− ... − αqi
) = 0 (**)
for i = 1, 2, ..., k. So the number of zeroes in the top row of each IRi
Ci is
ti − p + 1.
Any labelling has the form CS. Therefore if x is a labelling,
x = C{
Θ A1p 0 . . . . Θ
Θ Θ . . . . . Θ
. . . . . . . .
. . . . . . . .
. . . . . . . .
Θ . . . . . . Θ
+
Θ A1(p+1) Θ . . . . Θ
Θ Θ . . . . . Θ
. . . . . . . .
. . . . . . . .
. . . . . . . .
Θ . . . . . . Θ
+ ...
+
Θ A1q1
Θ . . . . Θ
Θ Θ . . . . . Θ
. . . . . . . .
. . . . . . . .
. . . . . . . .
Θ . . . . . . Θ
+ ... +
Θ Θ . . . . . Θ
Θ Θ . . . . . Θ
. . . . . . . .
. . . . . . . .
. . . . . . . .
Θ . . . . . . Akp
T. Dinesh, T. V. Ramakrishnan 59
+ ... +
Θ Θ . . . . . Θ
Θ Θ . . . . . Θ
. . . . . . . .
. . . . . . . .
. . . . . . . .
Θ . . . . . . Akqk
}
where
A1p =
[
αp 0 . . . 0
]
,
A1(p+1) =
[
0 αp+1 0 . . 0
]
, ..., A1q1
=
[
0 . . . 0 αq1
]
,
...,
Akp =
[
αp 0 . . 0 0
]
, ..., Akqk
=
[
0 . . . 0 αqk
]
.
Case 1: char F = 2
(**) is automatically satisfied for each i. Therefore the elements of
the set of labellings for 0 are linearly independent. So the rank of the free
F -module of labellings for 0 is q1 − p + 1 + q2 − p + 1 + ... + qk − p + 1 =
(q1 + q2 + ... + qk) − kp + k = q1 + q2 + ... + qk − (p − 1)k by Theorem 6.
Case 2: G is completely bipartite
Since G is Ri-bipartite for each i, the top elements of IRi
Ci correspond-
ing to the Ri-edges outside the spanning Ri-tree will be 0 for i = 1, 2, ..., k.
So (**) is irrelevant and hence the elements of the set of labellings for 0 are
linearly independent. Therefore the rank of the free F -module of labellings
for 0 is q1 −p+1+ q2 −p+1+ ...+ qk −p+1 = (q1 + q2 + ...+ qk)−kp+k
= q1 + q2 + ... + qk − (p − 1)k by Theorem 6.
Case 3: G is not completely bipartite and char F 6= 2
Subcase 1: G is not Ri-bipartite for i = 1, 2, ..., k
In this case, due to (**), one of the matrices can be expressed as a
linear combination of others for each i. So the rank of the free F -module
of labellings for 0 is q1 − p + q2 − p + ... + qk − p = (q1 + q2 + ... + qk) − kp
by theorem 6.
60 Labelling matrices of a graph structure
Subcase 2: G is Ri-bipartite for i = i1, i2, ..., ir, 1 < r < k and
not Ri-bipartite for i = ir+1, ..., ik; i1, i2, ..., ik ∈ {1, 2, ..., k}
In this case, due to (**), one of the matrices can be represented as a
linear combination of others for each i except for i = i1, i2, ..., ir. so the
rank of the free F -module of labellings for 0 is (q1 + q2 + ... + qk) − kp + r
by Theorem 6.
References
[1] A.E. Brouwer, A note on magic graphs, Report ZN 47/72(Internal communication),
Mathematisch Centrum, Amsterdam, 1972.
[2] D. Cartwright and F. Harary, Structural balance: a generalization of Heider’s theory,
Psychological Review, 63, 1956, pp. 277-293.
[3] T. Dinesh and T.V. Ramakrishnan, Ri-labellings and Ri-index vectors of a graph
structure, Adv. Appl. Discrete Math., 7(1), 2011, pp. 63-82.
[4] M. Doob, Generalizations of magic graphs, J. Combin. Theory Ser. B17, 1974,
pp.205-217.
[5] L. Euler, Solutio problematis ad geometriam situs pertinentis, Comment. Academiae
Sci. I. Petropolitanae, 8, 1736, pp. 128-140.
[6] S. Florini and Robin James Wilson, Edge-colourings of graphs, Research Notes in
Mathematics, London:Pitman, 16, 1977.
[7] F. Harary, Graph Theory, Narosa Pub. House, 1995.
[8] R.H. Jeurissen, The incidence matrix and labelings of a graph, J. Combin. Theory
Ser. B30, 1981, pp.290-301.
[9] E. Sampathkumar, Generalised graph structures, Bull. Kerala Math. Assoc., 3(2),
2006, pp.65-123.
[10] B.M. Stewart, Magic graphs, Canad. J. Math. 18, 1966, pp.1031-1059.
[11] T. Zaslavsky, Characterizations of signed graphs, J. Graph Theory, 5, 1981, pp.401-
406.
[12] T. Zaslavsky, Signed graphs, Discrete Appl. Math., 4(1), 1982, pp. 47-74.
Contact information
T. Dinesh Department of Mathematics,
Nehru Arts and Science College,
Padannakkad P.O., Kasaragod District - 671
314, Kerala, India
E-Mail: dineshthek@gmail.com
T. V. Ramakrish-
nan
Department of Mathematics,
S.E.S. College, Sreekandapuram, Kannur Dis-
trict - 670 631, Kerala, India
E-Mail: ramakrishnantvknr@gmail.com
Received by the editors: 25.07.2011
and in final form 29.05.2012.
|
| id | nasplib_isofts_kiev_ua-123456789-152307 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-01T20:42:24Z |
| publishDate | 2013 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Dinesh, T. Ramakrishnan, T.V. 2019-06-09T17:13:28Z 2019-06-09T17:13:28Z 2013 Labelling matrices and index matrices of a graph structure / T. Dinesh, T. V. Ramakrishnan // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 1. — С. 42–60. — Бібліогр.: 12 назв. — англ. 1726-3255 2010 MSC:05C07,05C78. https://nasplib.isofts.kiev.ua/handle/123456789/152307 The concept of graph structure was introduced by E. Sampathkumar in 'Generalised Graph Structures', Bull. Kerala Math. Assoc., Vol 3, No.2, Dec 2006, 65-123. Based on the works of Brouwer, Doob and Stewart, R.H. Jeurissen has ('The Incidence Matrix and Labelings of a Graph', J. Combin. Theory, Ser. B30 (1981), 290-301) proved that the collection of all admissible index vectors and the collection of all labellings for 0 form free F-modules (F is a commutative ring). We have obtained similar results on graph structures in a previous paper. In the present paper, we introduce labelling matrices and index matrices of graph structures and prove that the collection of all admissible index matrices and the collection of all labelling matrices for 0 form free F-modules. We also find their ranks in various cases of bipartition and char F (equal to 2 and not equal to 2). en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Labelling matrices and index matrices of a graph structure Article published earlier |
| spellingShingle | Labelling matrices and index matrices of a graph structure Dinesh, T. Ramakrishnan, T.V. |
| title | Labelling matrices and index matrices of a graph structure |
| title_full | Labelling matrices and index matrices of a graph structure |
| title_fullStr | Labelling matrices and index matrices of a graph structure |
| title_full_unstemmed | Labelling matrices and index matrices of a graph structure |
| title_short | Labelling matrices and index matrices of a graph structure |
| title_sort | labelling matrices and index matrices of a graph structure |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/152307 |
| work_keys_str_mv | AT dinesht labellingmatricesandindexmatricesofagraphstructure AT ramakrishnantv labellingmatricesandindexmatricesofagraphstructure |