# Introduction of eigen values on relative character graphs.

[section]1. Introduction

In this paper, we consider the adjacency matrix for RC-graphs and the eigen values are taken into account and a handful of results are obtained. An RC-graph is a finite simple graph [GAMMA](G, H) whose vertices are the complex irreducible characters of G and any two vertices [phi] and [psi] are adjacent if and only if their restriction [[PHI].sub.A]and [[phi].sub.H] contain at least one irreducible character [theta] of H in common. The definition of adjacency matrix for RC- graphs is defined as follows.

[section]2. Definition of RC-graphs and main results

Let G denote any finite group and Irr(G) denote the set of distinct complex irreducible characters of G. Let H be any subgroup of G. Then the Relative Character graph [GAMMA](G, H) (RC-graph) is defined as follows:

The vertex set V is IrrG. Two vertices and are adjacent if and only if their restrictions and to H contain at least one irreducible (complex) character of H is common (note that and need not be irreducible, but break into a direct sum of H-irreducibles). We refer to [5] for character theory of groups an [4] for graph theory.

[section]3. Basic properties of RC-graphs

(3.1) [GAMMA](G, H) is the null - graph if and only if H = G.

(3.2) r(G, (1)) is complete. However, the converse is not true.

(3.3) [GAMMA](G, H) is regular if and only if it is complete.

(3.4) [GAMMA](G, H) is connected if and only if [Core.sub.G]H = (1), where [Core.sub.G]H is the largest normal subgroup of G contained in H.

(3.5) The connected components of [GAMMA](G, H) are completely studied. Two vertices [phi],[psi] lie in the same component if and only if [phi] [subset] [psi][[psi].sup.8] for some s [greater than or equal to] 1, where [psi] = the induced character [1.sup.G.sub.H]

(3.6) A group G is Frobenius if there is a nontrivial proper subgroup H such that H [intersection] [H.sup.[chi]] = (1) for all [chi] [not member of] H ([H.sub.[chi]] = [chi][H.sub.x-1]).

Then there exists a normal subgraph N such that G is the semidirect product NH. N is called the (unique) Frobenius kennel and H is called the (unique, upto contingency) Frobenius complement.

(3.7) [GAMMA](G, H) is a tree if and only if G = NH is Frobenius and N is elementary abelian of order [p.sub.m] and 0(H) = [p.sub.m] - 1.

(3.8) [GAMMA](G, H) is always triangulated.

(3.9) [GAMMA](G, H) is a naturally (edge) signed graph.

[section]4. The eigen value problem for RC-graphs

For any finite, simple, undirected graph [GAMMA] = [GAMMA](V,E), the adjacency matrix A = ([a.sub.ij]) is defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is well known that since A is a real symmetric matrix all its eigen values must be real. Order the eigen values as [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ...[greater than or equal to] [[lambda].sub.n], where [absolute value of V] = n.

Before seeing where we digress for these special RC-graphs, we shall start from where the original results coincide for RC-graphs.

Recall from (3.2) that when (1) denote the trivial subgroup of G, then [GAMMA](G, (1)) is the complete graph [K.sub.n].

Theorem 4.1. The eigen values of [GAMMA](G, (1)) are - 1 (repeated n - 1 times), n - 1. (Notice that the sum must be 0 since this sum equals the sum of diagonal entries of A which is trivially 0.)

Theorem 4.2. Let G be an abelian group of order G and let H be a subgroup of order h. Then the distinct eigen values of [GAMMA](G, H) are -1 and (g/h) - 1 where -1 is repeated g - h times and (g/h) - 1 is repeated h times.

Proof. First note that by Lagrange's theorem g/h is an integer. It is known that (i) [GAMMA](G, H) is a graph with g vertices and h connected components and (ii) each component is the complete graph [K.sub.g/h] (see eg. [3]).

We can rearrange the vertices of V such that the matrix A breaks into h blocks, where the [i.sup.th] block is the g/h x g/h adjacency matrix of the [i.sup.th] component [K.sub.i] and the other block are 0's, 1 [less than or equal to] i [less than or equal to] h.

Clearly the eigen values of [GAMMA](G, H) are those of [K.sub.g/h], repeated h times. Since the eigen values of [K.sub.g/h] are -1, -1,..., -1, (g/h) - 1 (-1 repeated (g/h) - 1 times), overall, -1 is repeated h(g/h - 1) = g - h times and (g/h) - 1 is repeated h times.

Hence the theorem.

[section]5. The case when G is non-abelian

When H is the trivial subgroup, then [GAMMA](G, H) is complete and this case is already taken care of. Hence we can assume that H is non-trivial.

There are two approaches. First, to settle with reasonable bounds for the eigen values for arbitrary pair (G, H). Second is to take special groups and subgroups and actually compute the eigen values. We shall take up the second route in this paper.

The Frobenius groups

Let G = NH be a Frobenius group. That means, H is a (non-normal) subgroup such that H [intersection] [H.sup.[chi]] = (1) and N is normal defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As examples we have [S.sub.3], [A.sub.4], the dihedral group [D.sub.2m], m odd. For properties and character theory of G, we refer to [4].

The set IrrG is the disjoin union A [union] B, when

A = {[phi]|Ker[phi] [contains] N},

B = {[phi]|Ker[phi] [not contains] N}.

Theorem 5.1.[3] (i) The graph [GAMMA](G, H) is connected, [absolute value of V] = a + b where a = [absolute value of A] = [absolute value of IrrH] and b = [absolute value of B] = t/h(t + 1) = [absolute value of IrrH] and [absolute value of H] = h.

(ii) [GAMMA](G, H) contains [K.sub.b] as a complete subgraph and the remaining a vertices are such that each one is adjacent to every vertex in [K.sub.b].

(iii) None of these a vertices (which include [I.sub.G]) are adjacent among themselves.

Theorem 5.2. Let G = NH be Frobenius, such that [absolute value of B] > 1. Then the eigen values of the adjacency matrix of [GAMMA](G,H) constitute the set: {0 (repeater) a -1 times) -1 (repeated b times) and b}.

Proof. The vertices can be arranged in such a way that the first a vertices are taken from A (in some order) and the next b vertices are taken from B (in some order).

Then the adjacency matrix A is of the form:

(1) The top left corner has a x a zero matrix block.

(2) The remaining diagonal entries are 0's.

(3) All other entries are 1's.

By simple matrix manipulations, the eigen values, as stated in the theorem, can be easily found.

Example 5.3. Let G = [D.sub.10] = [C.sub.5] * [C.sub.2], where [D.sub.10] is the Dihedral group of 10 elements, [C.sub.2] and are cyclic subgroups of orders 2 and 5 respectively, with normal (Frobenius Kernel) and non-normal (Frobenius complement). We take H = [C.sub.2].

Then is the following graph: A = {[V.sub.1],[V.sub.2]}, B = {[V.sub.3],[V.sub.4]}.

[ILLUSTRATION OMITTED]

The matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The eigen values are {0, -1, -1, 2}. There are some special Frobenius groups for which {GAMMA](G, H) become trees.

Theorem 5.4. Let G = NH be Frobenius so that [absolute value of B] = 1. Then [GAMMA](G, H) is a star and the eigen values of A are : {0 (repeated a - 1 times and [+ or -][square root of d] where d is the degree of the middle vertex}.

Proof. In this case, all rows of A, except the last have 0's everywhere except 1 at the last column. The last row has 1's everywhere, except a 0 at the last place. Then [absolute value of [lambda] I - A] = [[lambda].sup.a-I]([[lambda].sup.2] - d). Thus the eigen values are: 0 (repeated a -1 times and [pi][square root of d]).

Example 5.5. Let G = [A.sub.4] = [V.sub.4] * [C.sub.3], where V is the Klein- four groups. Take H = [C.sub.3]. Then [GAMMA](G, H) is the following star.

[ILLUSTRATION OMITTED]

A = {[v.sub.1], [v.sub.2], [v.sub.3]}, B = {[v.sub.4]}.

Here [v.sub.1][v.sub.2] and [v.sub.3] have character degrees 1 and [v.sub.4] has character degree 3. The eigen values are {0,0, [+ or -][square root of 3]}.

It is remarkable that the only RC-graphs which are trees are stars! It is indeed a difficult job to fix the eigen values for arbitrary [GAMMA](G, H). However we get some reasonable bounds for a well-known class of groups and subgroups. Lemma 5.6. Let G be an arbitrary group and H, a nontrivial subgroup. Let the right action of G on G/H be doubly transitive. Then

(i) [GAMMA](G, H) consists of a subgraph T together with the trivial character adjacent to a unique vertex [phi][member of] T.

(ii) The eigen values [GAMMA](G, H) are caught up in the following inequalities:

[[lambda].sub.i]([GAMMA]) [greater than or equal to] [[lambda].sub.i]([GAMMA] - {v}) [greater than or equal to] [[lambda].sub.i+1]([GAMMA]) (1 [less than or equal to] i [less than or equal to] n - 1).

Proof. The first part of the statement is already well known (see eg. [3]). For (ii) we use the corresponding result in [7].

Theorem 5.7. Let G = PSLC(2, q), q = [p.sup.n], p a prime, H = Borel subgroup B of order q(q - 1). Then we get the following bounds for the eigen values of the adjacency matrix A of [GAMMA](G, H),

[[lambda].sub.1][greater than or equal to] n-1 [greater than or equal to] [[lambda].sub.2] [greater than or equal to] -1,

[[lambda].sub.3] [greater than or equal to] [[lambda].sub.4] [greater than or equal to] *** [greater than or equal to] [[lambda].sub.n-1] = 1, [[lambda].sub.n] = -1.

Proof. The graph [GAMMA](G,H) consists of the complete subgraph [K.sub.n-1] together with the vertex [1.sub.G] adjacent to a unique vertex of [K.sub.n-1].

Then taking v as the vertex corresponding to [1.sub.G] and using the result of [8], and Lemma 5.6, we immediately get our results.

[section]6. Laplace graphs

The Laplace Graph L = D - A, where D is the diagonal matrix whose [(i,i).sup.th] entry is the vertex degree [d.sub.i].

Theorem 6.1. The cofactors of L have a common value k which also equals the number of spanning trees of L (this is the famous Matrix - Tree Theorem). From this result, we can also derive the following results. Corollary 6.2.

(i) nk = [[mu].sub.1] [[mu].sub.2]... [[mu].sub.n-i] where [[mu].sub.1] [greater than or equal to] [[mu].sub.2] [greater than or equal to] ...[greater than or equal to] [[mu].sub.n] = 0 are the eigen values of L.

(ii) L is connected if and only if [[mu].sub.n-1] > 0.

There is a special case where in our [GAMMA](G, H) graph, the graph degree of each vertex is equal to the degree of that vertex as an irreducible character. This occurs for instance when [GAMMA](G, H) is a tree (star), with an additional property on H.

Theorem 6.3. Let G = NH be a Frobenius group such that

(i) N is elementary abelian of order [p.sup.m].

(ii) 0(H) = [p.sup.m] - 1.

(iii) H is abelian. Then for every vertex of [GAMMA](G,H), the character degree is the same as the graph degree.

Proof. First recall that the graph is a star and hence-except the middle vertex, all order vertices have graph degree one. But since H is abelian and hence every irreducible character [[phi].sub.i] has degree one, by the property of Frobenius groups, all these [[phi].sub.i] can be 'lifted' as irreducible characters of G as well. Hence the character degree of each pendent vertex [v.sub.i] = graph degree of [v.sub.i]. Finally let [psi] denote the middle vertex of [GAMMA](G,H). Then, graph degree [psi] = number of pendant vertices = order of H = character degree of [psi]. Hence the theorem.

Remark 6.4. There are other cases where these two degrees precisely coincide. For instand let G = [S.sub.4] and H = [S.sub.3] (sitting inside [S.sub.4]). Then [GAMMA](G, H), is the following graph.

[ILLUSTRATION OMITTED]

Now the vertex degree of [GAMMA](G, H) are {1,1, 2, 3, 3}. It is remarkable that the corresponding character degrees are also 1, 1, 2, 3 and 3.

Theorem 6.5. For all the above cases, we can replace the graph degrees in L by the corresponding character degrees and still maintain the same properties and get the same results.

[section]7. Future directions

We propose the following directions in which this study of eigen value problem for RCgraphs can be extended.

1. Put [L.sup.*] = [D.sup.*] - A where [D.sup.*] is the diagonal matrix when [(i,i).sup.th]-entry is equal to the character degree of the vertex [v.sub.i] (corresponding to the [i.sup.th] irreducible character study [[phi].sub.i]) the eigen value problem for [L.sup.*].

2. The group G acts on the set IrrG by conjugation (If [phi] [member of] IrrG, [phi] [member of] IrrG where [[phi].sup.g]([chi]) = [phi](g x [g.sup.-1])). This action also preserves the adjacency property: [phi] is adjacent to [psi] if and only if [[phi].sup.g] is adjacent to [[psi].sup.g]. In this sense, our RC-graph becomes a pseudo-homogenous graphs, generalizing the classical definition of homogeneous graphs. One can initiate a study of eigen value problem in the context of (Pseudo-homogenous) RC-graphs, following the works of F. R. K. Chang [1], [2] and others.

3. One can use QR-Factorization to obtain deeper and finer bounds for the eigen values of general RC-graphs, in particular, when G is non-abelian simple.

References

[1] F. R. K. Chung, Eigen values of graphs, proceeding of ICM, Zurich, 1994, 1333-1342.

[2] Lectures on Spectral Graph Theory, CBMS Lecture Notes, AMS Publications, 1995.

[3] T. Gnanaseelan, Studies in algebraic groups and representations, Ph. D. Thesis, Madurai Kamaraj University, Madurai (India), 2000.

[5] M. Isaacs, Character theory of Finite graphs, Academic Press, New York, 1969.

[6] A. V. Jeyakumar, Construction of some new finite graphs using group representations, In: Graphs, Combinatorics, Algorithms and Applications (Eds: S. Arumugam, B. D. Acharya and S. B. Rao), 49-58. Narosa Publishing House, New Delhi, 2004.

[7] H. Yuan, Bounds of Eigen values of a graph, Acta Mathematics Applicatae Sinica, Vol. 4, 165-168.

R. Stella Maragatham ([dagger]) and A. Vincent Jeyakumar ([double dagger])

([dagger]) Department of Mathematics, Queen Mary's College, Chennai-4, Tamil Nadu, India

([double dagger]) Department of Computer Science, Periyar Maniammai University, Tanjore Tamil Nadu, India E-mail: r_stellae@yahoo.co.in Avjeyakumar2004@yahoo.com