Skip to main content

Full text of "Mathematical Combinatorics. An International Book Series, vol. 2, 2012"

See other formats







Vol.1, 2012 ISBN 978-1-59973-186-5 


Mathematical Combinatorics 
(International Book Series) 


Edited By Linfan MAO 


The Madis of Chinese Academy of Sciences 


June, 2012 


Aims and Scope: TThe Mathematical Combinatorics (International Book Series) 
(ISBN 978-1-59978-186-5) is a fully refereed international book series, published in USA quar- 
terly comprising 100-150 pages approx. per volume, which publishes original research papers 
and survey articles in all aspects of Smarandache multi-spaces, Smarandache geometries, math- 
ematical combinatorics, non-euclidean geometry and topology and their applications to other 
sciences. Topics in detail to be covered are: 


Smarandache multi-spaces with applications to other sciences, such as those of algebraic 
multi-systems, multi-metric spaces,---, etc.. Smarandache geometries; 

Differential Geometry; Geometry on manifolds; 

Topological graphs; Algebraic graphs; Random graphs; Combinatorial maps; Graph and 
map enumeration; Combinatorial designs; Combinatorial enumeration; 

Low Dimensional Topology; Differential Topology; Topology of Manifolds; 

Geometrical aspects of Mathematical Physics and Relations with Manifold Topology; 

Applications of Smarandache multi-spaces to theoretical physics; Applications of Combi- 
natorics to mathematics and theoretical physics; 

Mathematical theory on gravitational fields; Mathematical theory on parallel universes; 

Other applications of Smarandache multi-space and combinatorics. 


Generally, papers on mathematics with its applications not including in above topics are 
also welcome. 
It is also available from the below international databases: 


Serials Group/Editorial Department of EBSCO Publishing 
10 Estes St. Ipswich, MA 01938-2106, USA 
Tel.: (978) 356-6500, Ext. 2262 Fax: (978) 356-9371 
http://www.ebsco.com/home/printsubs/priceproj.asp 

and 
Gale Directory of Publications and Broadcast Media, Gale, a part of Cengage Learning 
27500 Drake Rd. Farmington Hills, MI 48331-3535, USA 
Tel.: (248) 699-4253, ext. 1326; 1-800-347-GALE Fax: (248) 699-8075 
http://www.gale.com 


Indexing and Reviews: Mathematical Reviews(USA), Zentralblatt fur Mathematik(Germany), 
Referativnyi Zhurnal (Russia), Mathematika (Russia), Computing Review (USA), Institute for 
Scientific Information (PA, USA), Library of Congress Subject Headings (USA). 


Subscription A subscription can be ordered by an email to 7. mathematicalcombinatorics @gmail.com 
or directly to 


Linfan Mao 

The Editor-in-Chief of International Journal of Mathematical Combinatorics 
Chinese Academy of Mathematics and System Science 

Beijing, 100190, P.R.China 


Email: maolinfan@163.com 


Price: US$48.00 


Editorial Board (2nd) 


Editor-in-Chief 


Linfan MAO 

Chinese Academy of Mathematics and System 
Science, P.R.China 

and 

Beijing University of Civil Engineering and Ar- 
chitecture, P.R.China 

Email: maolinfan@163.com 


Editors 


S.Bhattacharya 

Deakin University 

Geelong Campus at Waurn Ponds 

Australia 

Email: Sukanto.Bhattacharya@Deakin.edu.au 


Dinu Bratosin 
Institute of Solid Mechanics of Romanian Ac- 


ademy, Bucharest, Romania 


Junliang Cai 
Beijing Normal University, P.R.China 


Email: caijunliang@bnu.edu.cn 


Yanxun Chang 
Beijing Jiaotong University, P.R.China 


Email: yxchang@center.njtu.edu.cn 


Shaofei Du 
Capital Normal University, P.R.China 


Email: dushf@mail.cnu.edu.cn 


Xiaodong Hu 
Chinese Academy of Mathematics and System 
Science, P.R.China 


Email: xdhu@amss.ac.cn 


Yuanqiu Huang 
Hunan Normal University, P.R.China 
Email: hyqq@public.cs.hn.cn 


H.Iseri 
Mansfield University, USA 
Email: hiseri@mnsfld.edu 


Xueliang Li 
Nankai University, P.R.China 


Email: lxl@nankai.edu.cn 


Guodong Liu 
Huizhou University 
Email: Igd@hzu.edu.cn 


Ion Patrascu 
Fratii Buzesti National College 


Craiova Romania 


Han Ren 
East China Normal University, P.R.China 


Email: hrenQ@math.ecnu.edu.cn 


Ovidiu-Tlie Sandru 
Politechnica University of Bucharest 


Romania. 


Tudor Sireteanu 
Institute of Solid Mechanics of Romanian Ac- 


ademy, Bucharest, Romania. 


W.B.Vasantha Kandasamy 
Indian Institute of Technology, India 


Email: vasantha@iitm.ac.in 


Luige Vladareanu 
Institute of Solid Mechanics of Romanian Ac- 


ademy, Bucharest, Romania 


Mingyao Xu 

Peking University, P.R.China 

Email: xumy@math.pku.edu.cn 

Guiying Yan 

Chinese Academy of Mathematics and System 
Science, P.R.China 

Email: yanguiying@yahoo.com 

Y. Zhang 


Department of Computer Science 
Georgia State University, Atlanta, USA 


Only those who dare to fail greatly can ever achieve greatly. 


By John Kennedy, the 35th President of the United States. 


Math. Combin. Book Ser. Vol.2(2012), 1-8 


Neutrosophic Rings IT 


Agboola A.A.A., Adeleke E.O. and Akinleye S.A. 


(Department of Mathematics, University of Agriculture, Abeokuta, Nigeria) 
E-mail: aaaola2003@yahoo.com, yemi376@yahoo.com, akinleyesa@yahoo.com 


Abstract: This paper is the continuation of the work started in [12]. The present paper 
is devoted to the study of ideals of neutrosophic rings. Neutrosophic quotient rings are also 


studied. 


Key Words: Neutrosophic ring, neutrosophic ideal, pseudo neutrosophic ideal, neutro- 


sophic quotient ring. 


AMS(2010): 03B60, 12E05, 97H40 


§1. Introduction 


The concept of neutrosophic rings was introduced by Vasantha Kandasamy and Florentin 
Smarandache in [1] where neutrosophic polynomial rings, neutrosophic matrix rings, neutro- 
sophic direct product rings, neutrosophic integral domains, neutrosophic unique factorization 
domains, neutrosophic division rings, neutrosophic integral quaternions, neutrosophic rings of 
real quarternions, neutrosophic group rings and neutrosophic semigroup rings were studied. In 
[12], Agboola et al further studied neutrosophic rings. The structure of neutrosophic polynomial 
rings was presented. It was shown that division algorithm is generally not true for neutrosophic 
polynomial rings and it was also shown that a neutrosophic polynomial ring (RU I) [a] can- 
not be an Integral Domain even if R is an Integral Domain. Also in [12], it was shown that 
(RU I) [x] cannot be a unique factorization domain even if R is a unique factorization domain 
and it was also shown that every non-zero neutrosophic principal ideal in a neutrosophic poly- 
nomial ring is not a neutrosophic prime ideal. The present paper is however devoted to the 


study of ideals of neutrosophic rings and neutrosophic quotient rings are also studied. 


§2. Preliminaries and Results 


For details about neutrosophy and neutrosophic rings, the reader should see [1] and [12]. 


Definition 2.1 Let (R,+,-) be any ring. The set 
(RUI) ={a+bl:a,b€ R} 


is called a neutrosophic ring generated by R and I under the operations of R, where I is the 
neutrosophic element and I? = I. 


1Received March 14, 2012. Accepted June 2, 2012. 


2 Agboola A.A.A., Adeleke E.O. and Akinleye S.A. 


If (RUD) = (Zn UT) with n < 00, then 0((Z, UI)) = n?. Such a (RU) is said to be a 
commutative neutrosophic ring with unity if rs = sr for all r,s € (RU J) and 1 € (RUD). 


Definition 2.2 Let (RU I) be a neutrosophic ring. A proper subset P of (RLJI) is said to be 
a neutrosophic subring of (RU I) if P=(SUnI), where S is a subring of R and n an integer, 
P is said to be generated by S and nI under the operations of R. 


Definition 2.3 Let (RUI) be a neutrosophic ring and let P be a proper subset of (RU 1) 
which is just a ring. Then P is called a subring. 


Definition 2.4 Let T be a non-empty set together with two binary operations + and -. T is 


said to be a pseudo neutrosophic ring if the following conditions hold: 


(1) T contains elements of the form a+ bl, where a and b are real numbers and b # 0 for 
at least one value; 

(2) (T,+) is an abelian group; 

(3) (L,-) is a semigroup; 

(4) Va,y,z2€T, e(y+2z) =ayt+ az and (yt z)a =yust zu. 


Definition 2.5 Let (RU JI) be any neutrosophic ring. A non-empty subset P of (RU I) is said 
to be a neutrosophic ideal of (RI) if the following conditions hold: 


(1) P is a neutrosophic subring of (RUD); 
(2) for everyp € P andr € (RU), rp € P and pr € P. 


If only rp € P, we call P a left neutrosophic ideal and if only pr € P, we call P a right 
neutrosophic ideal. When (RU I) is commutative, there is no distinction between rp and pr 
and therefore P is called a left and right neutrosophic ideal or simply a neutrosophic ideal of 


(RUD). 


Definition 2.6 Let (RU JI) be a neutrosophic ring and let P be a pseudo neutrosophic subring 
of (RU I). P is said to be a pseudo neutrosophic ideal of (RU I) if Vp € P andr € (RUD), 
rp, pre P. 


Example 2.7 Let (Z UI) be a neutrosophic ring of integers and let P = (nZ UI) for a positive 
integer n. Then P is a neutrosophic ideal of (Z U I). 


y 


z 


Example 2.8 Let (RU J) = : 2,y,z © (RUT) ? be the neutrosophic ring of 2 x 2 


y 
0 


matrices and let P = : ay © (RUT) >. Then P is a neutrosophic ideal of (ZU I). 


Theorem 2.9 Let (Z,UI) be a neutrosophic ring of integers modulo p, where p is a prime 
number. Then: 


(1) (Z, UL) has no neutrosophic ideals and 
(2) (Zp, UL) has only one pseudo neutrosophic ideal of order p. 


Neutrosophic Rings II 3 


Proposition 2.10 Let P, J and Q be neutrosophic ideals (resp. pseudo neutrosophic ideals) 
of a neutrosophic ring (RUT). Then 


1) P+ J is a neutrosophic ideal (resp. pseudo neutrosophic ideal) of (RU I); 
2) PJ is a neutrosophic ideal (resp. pseudo neutrosophic ideal) of (RU I); 


3) PO J is a neutrosophic ideal (resp. pseudo neutrosophic ideal) of (RU I); 
4) PQ) = (PJ)Q; 
5) PO +Q) =P + PQ; 


(1) 
(2) 
(3) 
(4) 
(5) 
(6) 





6) (J+ Q)P=JP+QP. 











Proof The proof is the same as in the classical ring. 





Proposition 2.11 Let (RUT) be a neutrosophic ring and let P be a subset of (RUT) t. Then 
P is a neutrosophic ideal (resp. pseudo neutrosophic ideal) iff the following conditions hold: 


(1) P40; 
(2)a,be P=a-—beP; 
(3)aE Pre (RUI) Sra,ar € P. 











Proof the proof is the same as in the classical ring. 





Proposition 2.12 Let (RUT) be any neutrosophic ring. Then (RUT) and < 0 > are neutro- 
sophic ideals of (RUT). 


Proposition 2.13 Let (RUT) be a neutrosophic ring with unity (no unit in (RUT) since 
I~" does not exist in (RUI)) and let P be a neutrosophic ideal of (RUI). If 1 € P then 
=(RUI). 


Proposition 2.14 Let (RUT) be a neutrosophic ring with unity (no unit in (RUT) since I~+ 
does not exist in (RUI)) and let P be a pseudo neutrosophic ideal of (RUT). If1€ P then 
P#(RUI). 


Proof Suppose that P is a pseudo neutrosophic ideal of the neutrosophic ring (R U I) with 
unity and suppose that 1 € P. Let r be an arbitrary element of (R U I). Then by the definition 
of P, r.1 =r should be an element of P but since P is not a neutrosophic subring of (RU J), 
there exist some elements b = x + yI with x,y 4 0 in (RUT) which cannot be found in P. 
Hence P 4 (RU I). 














Proposition 2.15 Let (RUT) be a neutrosophic ring and leita =x+ yl be a fixed element of 
(RUT). Suppose that P= {ra:r€ (RUT)} is a subset of (RUT). 


(1) Ifz,y £0, then P is a left neutrosophic ideal of (R UI); 
(2) Ifa =0, then P is a left pseudo neutrosophic ideal of (RUT). 


Proof (1) is clear. For (2), if « = 0 then each element of P is of the form sI for some 
s € R. Hence P = {0, sI} which is a left pseudo neutrosophic ideal of (R U J). 














4 Agboola A.A.A., Adeleke E.O. and Akinleye S.A. 


Theorem 2.16 Every ideal of a neutrosophic ring (RUT) is either neutrosophic or pseudo 


neutrosophic. 


Proof Suppose that P is any ideal of (R UJ). If P 4 (0) or P# (RU J), then there exists 
a subring S of R such that for a positive integer n, P=< SUnI >. Letp€ Pandreé (RUI). 
By definition of P, rp,pr € P and the elements rp and pr are clearly of the form a+ b/ with 
at least b 4 0. 














Definition 2.17 Let (RUT) be a neutrosophic ring. 


(1) If P is a neutrosophic ideal of (RUT) generated by an element r =a+bI € (RUT) 
with a,b #0, then P is called a neutrosophic principal ideal of (RU I), denoted by (r). 

(2) If P is a pseudo neutrosophic ideal of (R UTI) generated by an element r = aI € (RUT) 
with a #0, then P is called a pseudo neutrosophic principal ideal of (RUT), denoted by (r). 


Proposition 2.18 Let (RU I) be a neutrosophic ring and letr = a+bI € (RUT) with a,b 40. 


(1) (r) is the smallest neutrosophic ideal of (R UTI) containing r; 
(2) Every pseudo neutrosophic ideal of (RUT) is contained in some neutrosophic ideal of 
(RUT). 


Proposition 2.19 Every pseudo neutrosophic ideal of (Z UTI) is principal. 


Definition 2.20 Let (RUT) be a neutrosophic ring and let P be a neutrosophic ideal (resp. 
pseudo neutrosophic ideal) of (RUT). 


(1) P is said to be maximal if for any neutrosophic ideal (resp. pseudo neutrosophic ideal) 
J of (RUT) such that P C J we have either J= M or J=(RUI). 

(2) P is said to be a prime ideal if for any two neutrosophic ideals (resp. pseudo neutro- 
sophic ideals) J and Q of (RU I) such that JQ C P we have either JC P or QC P. 


Proposition 2.21 Let (RUT) be a commutative neutrosophic ring with unity and let P be a 
neutrosophic ideal (resp. pseudo neutrosophic ideal) of (RUT). Then P is prime iff xy © P 
with « and y in (RUT) implies that either x € P ory€ P. 


Example 2.22 In (ZU) the neutrosophic ring of integers: 


(1) (nI) where n is a positive integer is a pseudo netrosophic principal ideal. 
(2) (Z) is the only maximal pseudo neutrosophic ideal. 
(3) (0) is the only prime neutrosophic ideal (resp. prime pseudo neutrosophic ideal). 


Definition 2.23 Let (RUT) be a commutative neutrosophic ring and let ¢ = a+ bI be an 
element of (RUT) with a,be R. 


(1) If a,b 4 0 and there exists a positive integer n such that x” = 0 then x is called a 
strong neutrosophic nilpotent element of (RUT). 
(2) Ifa=0,b40 and there exists a positive integer n such that x” = 0 then x is called a 


weak neutrosophic nilpotent element of (RUT). 


Neutrosophic Rings II 5 


(3) If b = 0 and there exists a positive integer n such that x” = 0 then x is called an 


ordinary nilpotent element of (RUT). 


Example 2.24 In the neutrosophic ring (Z,U J) of integers modulo 4, 0 and 2 are ordinary 
nilpotent elements, 2/ is a weak neutrosophic nilpotent element and 2 + 2/ is a strong neutro- 
sophic nilpotent element. 


Proposition 2.25 Let (RUT) be a commutative neutrosophic ring. 


(1) The set of all strong neutrosophic nilpotent elements of (RUT) is not a neutrosophic 
ideal. 

(2) The set of all weak neutrosophic nilpotent elements of (RUT) is not a neutrosophic 
ideal. 

(3) The set of all nilpotent (ordinary, strong and weak neutrosophic) elements of the com- 


mutative neutrosophic ring (RU I) is a neutrosophic ideal of (RU I). 


Definition 2.26 Let (RU I) be a neutrosophic ring and let P be a neutrosophic ideal of (RUT). 
Let (RUI)/P be a set defined by 


(RUD) /P={r+P:re(RUD}. 
If addition and multiplication in (RU I) /P are defined by 


(r+ P)+(s+P)=(r+s)+P, 
(r+ P)(s+P)=(rs)+P,r,pe (RU), 


it can be shown that (RU I) /P is a neutrosophic ring called the neutrosophic quotient ring with 
P as an additive identity. 


Definition 2.27 Let (RU I) be a neutrosophic ring and let P be a subset of (RU I). 


(1) If P is a neutrosophic ideal of (RUI) and (RUT) /P is just a ring, then (RU I) /P 
is called a false neutrosophic quotient ring; 

(2) If P is a pseudo neutrosophic ideal of (RUI) and (RUI)/P is a neutrosophic ring, 
then (RU I) /P is called a pseudo neutrosophic quotient ring; 

(3) If P is a pseudo neutrosophic ideal of (RUI) and (RUI)/P is just a ring, then 
(RUT) /P is called a false pseudo neutrosophic quotient ring. 


Example 2.28 Let < Z,UJ >= {0,1,2,3,4,5, J, 21,37, 47,57,1+/,14+27,14+37,1+47,1+ 
61,24+/7,2+21,24+3/7,24+4/7,24+57,34+/,34+ 27,34+31,3+47,3+57,44 7,44 27,44 3/,44 
47,44+57,5+7,54+ 27,54 37,5+ 47,545} be a neutrosophic ring of integers modulo 6. 











(1) If P = {0,2, 7,27, 37,47, 57,2+/,2+27,2+37,2+4]7,2+5/}, then P is a neutrosophic 
ideal of < Zg UI > but < Zg UI > /P={P,1+P,34+P,4+P,5+4+ P} is just a ring and thus 
< Z,UI > /P isa false neutrosophic quotient ring. 

(2) If P = {0, 27,4}, then P is a pseudo neutrosophic ideal of < ZUJI > and the quotient 


ring 


6 Agboola A.A.A., Adeleke E.O. and Akinleye S.A. 


<Z,UI>/P={P14+P2+P,34+P44+P54+PIJ4+P,14+D4+P(24+)/D4+P,384D+ 
P,(4+1)+P,(5+J) + P} is a pseudo neutrosophic quotient ring. 

(3) If P = {0,/,27,37,47,5I}, then P is a pseudo neutrosophic ideal and the quotient 
ring. < Z.UI > /P={P1+P,2+P,3+P,44+ P,5+ P} is a false pseudo neutrosophic 


quotient ring. 


Definition 2.29 Let (RUT) and (SUI) be any two neutrosophic rings. The mapping ¢ : 
(RUT) > (SUT) is called a neutrosophic ring homomorphism if the following conditions hold: 


(1) ¢ is a ring homomorphism; 

(2) eZ) =I. 

If in addition @ is both 1—1 and onto, then @ is called a neutrosophic isomorphism and 
we write (RUT) = (SUT). 

The set {x € (RUT) : 6(x) = 0} is called the kernel of ¢ and is denoted by Kerd. 


Theorem 2.30 Let 6: (RUI) — (SUI) be a neutrosophic ring homomorphism and let 
K = Ker@ be the kernel of ¢. Then: 


(1) K ts always a subring of (RU I); 
(2) K cannot be a neutrosophic subring of (RU I); 
(3) K cannot be an ideal of (RU I). 


Example 2.31 Let (Z UI) be a neutrosophic ring of integers and let P = 5ZUI. It is clear that 
P is a neutrosophic ideal of (ZU I) and the neutrosophic quotient ring (Z U I) /P is obtained 
as 





(ZUD/P = {P1+P,2+P3+P4+P,I4+P,21+P,31+P,4I1+P, 
(1+D+P,(1+2N+Ph,14+3N+R1+4D+PR,2+D+P, 
(2421) +P,(24+3ND+P,(2+4)+P,(3+1D+P,(3+21) +P, 
(G4INEP BEANE RAED P44 2)4 P6443) +P 4a EP, 






































The following can easily be deduced from the example: 


(1) (ZU TJ) /P is neither a field nor an integral domain. 

(2) (Z UT) /P and the neutrosophic ring < Z; UI > of integers modulo 5 are structurally 
the same but then 

(3) The mapping ¢: (ZUI) — (ZU I) /P defined by ¢(z) = x+ P for all x € (ZU) is 
not a neutrosophic ring homomorphism and consequently (Z UI) 4 (Z UTI) /P ##< Z5,UI >. 

These deductions are recorded in the next proposition. 


Proposition 2.32 Let (Z UI) be a neutrosophic ring of integers and let P = (nZ UTI) where 


n is a positive integer. Then: 


(1) (ZUT) /P is a neutrosophic ring; 
(2) (ZUT) /P is neither a field nor an integral domain even if n is a prime number; 
(3) (ZU) /P # (ZU). 


Neutrosophic Rings II 7 


Theorem 2.33 If P is a pseudo neutrosophic ideal of the neutrosophic ring (Zp, UTI) of integers 
modulo n, then 
(Z, UT) /P & Zp. 


Proof Let P = {0,/,21,31,--- ,(m—3)I, (n— 2)I, (n—1)J}. It is clear that P is a pseudo 
neutrosophic ideal of (Z,, UI) and (Z, UI) /P is a false neutrosophic quotient ring given by 





(Z, UT) /P={P,14+P,2+P,3+P,---,(n—-3)+P,(n—2)+P,(n-1) +P} 2% Zn. 














Proposition 2.34 Let 6: (RUI) — (SUI) be a neutrosophic ring homomorphism. 


(1) The set ((RUJ)) = {g(r) :r € (RUD} is a neutrosophic subring of (SUI); 

(2) o(-r) =—9(r) Vr e (RUT); 

(3) If 0 is the zero of (RUT), then $(0) is the zero of ¢((RUI)); 

(4) If P is a neutrosophic ideal (resp. pseudo neutrosophic ideal) of (RU I), then o(P) is 
a neutrosophic ideal (resp. pseudo neutrosophic ideal) of (SU I); 

(5) If J is a neutrosophic ideal (resp. pseudo neutrosophic ideal) of (SUT), then ¢~1(J) 
is a neutrosophic ideal (resp. pseudo neutrosophic ideal) of (RU I); 

(6) If (RUT) has unity 1 and 6(1) £0 in (SUT), then $(1) is the unity o((RU J)); 

(7) If (RUT) is commutative, then d((RUI)) is commutative. 





Proof The proof is the same as in the classical ring. 











References 


[1] Vasantha Kandasamy W.B. and Florentin Smarandache, Neutrosophic Rings, Hexis, Phoenix, 
Arizona, 2006. 

[2] Vasantha Kandasamy W.B. and Florentin Smarandache, Some Neutrosophic Algebraic 
Structures and Neutrosophic N-Algebraic Structures, Hexis, Phoenix, Arizona, 2006. 

[3 


Vasantha Kandasamy W.B. and Florentin Smarandache, Basic Neutrosophic Algebraic 
Structures and their Applications to Fuzzy and Neutrosophic Models, Hexis, Church Rock, 
2004. 

4) Vasantha Kandasamy W.B., Gaussian polynomial rings, Octogon, vol.5, 58-59, 1997. 

5] Vasantha Kandasamy W.B., Inner associative rings, J. of Math. Res. and Expo., vol.18, 
217-218, 1998. 

6] Vasantha Kandasamy W.B., CN rings, Octogon, vol.9, 343-344, 2001. 

7| Vasantha Kandasamy W.B., On locally semi unitary rings, Octogon, vol.9, 260-262, 2001. 
8] Vougiouklis Thomas, On rings with zero divisors strong V-groups, Comment Math. Univ. 
Carolin J., vol.31, 431-433, 1990. 

9] Wilson John S., A note on additive subgroups of finite rings, J. Algebra, vol.234, 362-366, 
2000. 

[10] Florentin Smarandache, A Unifying Field in Logics: Neutrosophic Logic, Neutrosophy, 








Neutrosophic Set, Neutrosophic Probability, (3rd edition), American Research Press, Re- 
hoboth, 2003. 





11 


12 


13 


14 


15 


16 
17 





Agboola A.A.A., Adeleke E.O. and Akinleye S.A. 


Agboola A.A.A. and Akinola L.S., On the Bicoset of a Bivector Space, Int. J. of Math. 
Comb., vol.4, 1-8, 2009. 

Agboola A.A.A., Akinola A.D., and Oyebola O.Y., Neutrosophic Rings I, Int. J. of Math. 
Comb., vol.4, 1-14, 2011. 

Fraleigh, J.B., A First Course in Abstract Algebra (5th Edition), Addison-Wesley, 1994. 
Lang S., Algebra, Addison Wesley, 1984. 

Atiyah M.F. and MacDonald I.G., Introduction to Commutative Algebra, Addison-Wesley, 
1969. 

Herstein I.N., Topics in Algebra, John Wiley and Sons, 1964. 

Herstein I.N., Topics in Ring Theory, University of Chicago Press, 1969. 


Math. Combin. Book Ser. Vol.2(2012), 9-23 


Non-Solvable Spaces of Linear Equation Systems 


Linfan Mao 
(Chinese Academy of Mathematics and System Science, Beijing 100190, P.R.China) 
E-mail: maolinfan@163.com 


Abstract: A Smarandache system (X;R) is such a mathematical system that has at least 
one Smarandachely denied rule in R, i.e., there is a rule in (©; R) that behaves in at least 
two different ways within the same set ©, i.e., validated and invalided, or only invalided but 
in multiple distinct ways. For such systems, the linear equation systems without solutions, 
i.e., non-solvable linear equation systems are the most simple one. We characterize such non- 
solvable linear equation systems with their homeomorphisms, particularly, the non-solvable 
linear equation systems with 2 or 3 variables by combinatorics. It is very interesting that 
every planar graph with each edge a straight segment is homologous to such a non-solvable 


linear equation with 2 variables. 


Key Words: Smarandachely denied axiom, Smarandache system, non-solvable linear equa- 


tions, V-solution, A-solution. 


AMS(2010): 15A06, 68R10 
§1. Introduction 


Finding the exact solution of equation system is a main but a difficult objective unless the 
case of linear equations in classical mathematics. Contrary to this fact, what is about the 
non-solvable case? In fact, such an equation system is nothing but a contradictory system, 
and characterized only by non-solvable equations for conclusion. But our world is overlap and 
hybrid. The number of non-solvable equations is more than that of the solvable. The main 
purpose of this paper is to characterize the behavior of such linear equation systems. 

Let R™, R™ be Euclidean spaces with dimensional m, n > 1 and 7: R” x R” — R™ be 
a C*, 1 <k < oo function such that T(Zo, Jo) = 0 for Fo € R”, Jy € R™ and the m x m matrix 
OT! /Oy' (Zo, Fo) is non-singular, i.e., 

aet( >) | (Zoo) #0, wherel < i,j <m. 

Then the implicit function theorem ([1]) implies that there exist opened neighborhoods V Cc R” 
of Zo, W C R™ of J and a C* function ¢: V — W such that 


T(z, 6(@)) =0. 
Thus there always exists solutions for the equation T(Z, (y)) = 0 if T is C’, 1< k < oo. Now 
let T,,T2,--: ,Im, m> 1 be different C* functions R” x R™ — R™ for an integer k > 1. An 


1Received March 6, 2012. Accepted June 5, 2012. 


10 Linfan Mao 


equation system discussed in this paper is with the form following 


for all integers 1 < ig < m. Denoted by S$® the solutions of equation T;(Z,7) = 0 for integers 


m m 

1<i<m. Then U S$? and () 9° are respectively the V-solutions and A-solutions of equations 
j= i=l 

(Eq). By definition, we are easily knowing that the A-solution is nothing but the same as the 


classical solution. 


Definition 1.1 The V-solvable, \-solvable and non-solvable spaces of equations (Eq) are re- 


spectively defined by 


Us? () 3° and UJ s?- (8°. 
i=l i=l i=1 i=l 


Now we construct a finite graph G[Eq] of equations (Eq) following: 
V(G[Eq]) = {ull Sis m}, 


E(G[Eq)) = {(v, 09) 


Such a graph G[Eq] can be also represented by a vertex-edge labeled graph G"[Eq] following: 





A(Zo, Yo) > T; (Zo, Yo) =0A T; (Zo, Yo) =0,; 1 < 1, J ‘< m}. 


V(G*[Eq]) = {S2|1 <i < m}, 
E(G[Eq]) = {(S9, $9) labeled with S°()$9|S9 1 S9 40,1 < i,j < m}. 


4? J 
For example, let S? = {a,b,c}, S? = {c,d,e}, S$ = {a,c,e} and S$? = {d,e, f}. Then its 
edge-labeled graph G[Eq] is shown in Fig.1 following. 


{o} 
51) 8 





{a, c} 














Non-Solvable Spaces of Linear Equation Systems 11 


Notice that U) S$? = LU S?, ie., the non-solvable space is empty only if m = 1 in (Eq). 
i=1 i= 
Generally, let (1;R1) (S2;R2), --- ,(2mj;Rm) be mathematical systems, where R; is a rule 


on 4; for integers 1 <i < m. If for two integers i,j, 1 < i,j <m, 4; A 4; or L; = Uy but 
Ri # Rj, then they are said to be different, otherwise, identical. 





Definition 1.2((12]-[13]) A rule in R a mathematical system (U; R) is said to be Smarandachely 
denied if it behaves in at least two different ways within the same set %, 1.e., validated and 
invalided, or only invalided but in multiple distinct ways. 

A Smarandache system (X;R) is a mathematical system which has at least one Smaran- 
dachely denied rule in R. 


Thus, such a Smarandache system is a contradictory system. Generally, we know the 
conception of Smarandache multi-space with its underlying combinatorial structure defined 
following. 


Definition 1.3((8]-[10]) Let (21; R1), (H2; Re), +--+, (Um; Rm) bem > 2 mathematical spaces, 

different two by two. A Smarandache multi-space ¥ is a union U bj with rules R= U Ri on 
i=1 i=1 

ay i.e., the rule Ry on %; for integers 1<1<m, denoted by (E:R). 


Similarly, the underlying graph of a Smarandache multi-space (E:R) is an edge-labeled 
graph defined following. 


Definition 1.4((8]-[10]) Let (5:) be a Smarandache multi-space with © = U d; and R= 


w=1 


U R;. Its underlying graph G [E.R is defined by 
i=1 


V (c [5, R]) = {2n, Ue,-:-, Em}, 


B(G|5,R]) ={ (2,2,) | 2) 401 S45 sm} 
with an edge labeling 
IF: (X;,0;)€ E (c [S. R|) = 17(5,,5,) =o (2 =;) 
where w is a characteristic on X; (|X; such that U;() Xj is isomorphic to Xp () Xi if and only 


if @(Xi (25) = w (Ue f) 1) for integers 1 < i,j, k,l <m. 


We consider the simplest case, i.e., all equations in (Eq) are linear with integers m > n 
and m,n > 1 in this paper because we are easily know the necessary and sufficient condition of 
a linear equation system is solvable or not in linear algebra. For terminologies and notations 
not mentioned here, we follow [2]-[3] for linear algebra, [8] and [10] for graphs and topology. 

Let 


AX = (b1,bo,+-+ , bm)? (LEq) 


be a linear equation system with 


12 Linfan Mao 


Q11 a12  *** Gin Ty 
a21 G22 *** Gan v2 
A= and X = 
aml aAm2 oe Amn In 
for integers m, n > 1. Define an augmented matrix At of A by (b1,b2,--- , bm)? following: 

Q11 a12  *** Gin by 

At= a21 a22  *** G2n be 
aml aAm2 ee Amn bm 


We assume that all equations in (LFq) are non-trivial, i.e., there are no numbers \ such that 
(441, @i2,°++ , Qin, bs) = A(Qj1, Gj2,*-+ , jn, b;) 


for any integers 1 < i,7 <m. Such a linear equation system (LEq) is non-solvable if there are 
no solutions 7;, 1<i<n satisfying (LEq). 


§2. A Necessary and Sufficient Condition for Non-Solvable Linear Equations 


The following result on non-solvable linear equations is well-known in linear algebra((2]-[3]). 


Theorem 2.1 The linear equation system (LEq) is solvable if and only if rank(A) = rank(AT). 
Thus, the equation system (LEq) is non-solvable if and only if rank(A) 4 rank(AT). 


We introduce the conception of parallel linear equations following. 
Definition 2.2 For any integers 1<i,7 <m, i#j, the linear equations 


Q41 21 + AyQ%Q + +++ Ginn = bi, 


05121 + Aj2%2 + +++ AjnTn = b; 
are called parallel if there exists a constant c such that 
C= 451/Gi1 = Aj2/ai2 = +++ = Ajn/ Ain F b;/bi. 
Then we know the following conclusion by Theorem 2.1. 
Corollary 2.3 For any integers i,j, 1 #7, the linear equation system 


A412] + AQX2 + +++ AinTn = bi, 


Qj1 21 + Aj2v2 spite Ajntn = b; 


is non-solvable if and only if they are parallel. 


Non-Solvable Spaces of Linear Equation Systems 13 


Proof By Theorem 2.1, we know that the linear equations 


A412] + A272 + +++ AinTn = bi, 





aj1T1 1 AjQ2XQ aes AjnIn = b; 


is non-solvable if and only if rankA’ 4 rankB’, where 


Qt Gi2 *** Ain Gil iQ + Ain Dy 


A= , B= 


Qj1 Aj2 *** Ajn Qj1 GAj2 *** Ayn be 


It is clear that 1 < rankA’ < rankB’ < 2 by the definition of matrixes A’ and B’. Consequently, 
rankA’ = 1 and rankB’ = 2. Thus the matrix A’, B’ are respectively elementary equivalent to 


matrixes 
1 0 1 0 0 0 
0 0 Onl -Y |e 0 0 
ie., there exists a constant c such that ¢ = aj1/ai) = aj2/aig = +++ = Ajn/din but c F b;/by. 


Whence, the linear equations 


Qi1L1 + Ajg%2 + +++ GinEn = bi, 





Aj121 1 Aj2X2Q apie AjnIn = b; 














is parallel by definition. 


We are easily getting another necessary and sufficient condition for non-solvable linear 
equations (LEq) by three elementary transformations on a m x (n + 1) matrix At defined 
following: 


(1) Multiplying one row of At by a non-zero scalar c; 
(2) Replacing the ith row of At by row i plus a non-zero scalar c times row j; 
(3) Interchange of two row of AT. 


Such a transformation naturally induces a transformation of linear equation system (LEq), 
denoted by T(LEq). By applying Theorem 2.1, we get a generalization of Corollary 2.3 for non- 
solvable linear equation system (LEq) following. 


Theorem 2.4 A linear equation system (LEgq) is non-solvable if and only if there exists a 


composition T of series elementary transformations on A* with T(AT) the forms following 


td / / / 
Ay, AQ + Ay OY 
/ / / / 
G1 492, ++ Ag Dg 
T(At) = 
/ / / / 
aml am2 amn b 


14 Linfan Mao 


and integers 1, 7 with 1 <i,7 <m such that the equations 


/ / / / 
i121 + AjgL2 + +++ AinTn = b;, 


f: / / i 
Gy Ly + Ajg%Q 1+ Ain tn = by 
are parallel. 


Proof Notice that the solution of linear equation system following 


has exactly the same solution with (LEq). If there are indeed integers k and i, j with 1 < 
k,7,7 <m such that the equations 


/ / / / 
Ay T1 + Aigo +++ Ginn = bj, 


/ 


! / = it 
A511 + Ajo%2 +++ Ain Tn = b,; 


are parallel, then the linear equation system (LEq*) is non-solvable. Consequently, the linear 
equation system (LEq) is also non-solvable. 


Conversely, if for any integers k andi, j with 1 < k,i,7 < m the equations 


/ / / t 
ay T1 + ajo%2 + res Aintn = b,, 
! / ? ur 
5121 + Ajo%2 +++ Ain En = b; 


are not parallel for any composition T of elementary transformations, then we can finally get a 


linear equation system 











1, + C1 s41%ig4, Heo + C1 nt, = dh 
Lig + €2,541%1,4, t°°+ + CanX1, = de 

(LEq™*) 
ZX], T Cs,st+1Ule44 ste? + Cs.nt1, = ds 











by applying elementary transformations on (LEq) from the knowledge of linear algebra, which 
has exactly the same solution with (LEq). But it is clear that (LEgq**) is solvable, i.e., the 
linear equation system (LEq) is solvable. Contradicts to the assumption. 














This result naturally determines the combinatorial structure underlying a linear equation 
system following. 


Theorem 2.5 A linear equation system (LEgq) is non-solvable if and only if there exists a 


composition T of series elementary transformations such that 
G[T(LEq)] # Km, 


where Ky, is a complete graph of order m. 


Non-Solvable Spaces of Linear Equation Systems 15 


Proof Let T(A™) be 


/ / / / 
G1 G2 77° Ain 1 

/ / / / 
a a te 

21 22 2n 2 

T(At) = 

/ / / / 

Ami am2 a Qmn Din 


If there are integers 1 < i, 7 <_m such that the linear equations 


/ / / / 
Gj %1 + Ayg®q + +++ Ayn n = b;, 


/ / / / 
Ay Ly + Aygo + +++ Ain En = 05 


are parallel, then there must be S?(\S) = 0, where S?, S¥ are respectively the solutions of 
linear equations @j;%1 + @jg%2 + +++ @jn%n = 05 and ai,x1 + aijgx2 + +++ a5j,Xn = bi. Whence, 


there are no edges (S), S$) in G[LEq] by definition. Thus G[LEq] 4 Km. 














We wish to find conditions for non-solvable linear equation systems (LEq) without elemen- 
tary transformations. In fact, we are easily determining G[LEq] of a linear equation system 
(LEq) by Corollary 2.3. Let L; be the ith linear equation. By Corollary 2.3, we divide these 
equations L;, 1<%i< m into parallel families 


C1, G2,°°° 6s 


by the property that all equations in a family @; are parallel and there are no other equations 
parallel to lines in @; for integers 1 < i < s. Denoted by |@| = ni, 1 <i < s. Then the 
following conclusion is clear by definition. 


Theorem 2.6 Let (LEq) be a linear equation system for integers m,n >1. Then 


G[LEq| > Mas pean: sn 


s 


with ny t+n+24+---+n, = m, where ©; is the parallel family with n; = |@;| for integers 
1<i<s in (LEq) and (LEq) is non-solvable if s > 2. 


Proof Notice that equations in a family @; is parallel for an integer 1 < i < m and each of 


them is not parallel with all equations in U G. Let n; = |@;| for integers 1 <i < s in 
1<l<m fi 
(LEq). By definition, we know 


G[LEq| > ona sn 


s 


with nj +n+2+4+---+ng =m. 
Notice that the linear equation system (LEq) is solvable only if G[LEq| ~ Km by definition. 
Thus the linear equation system (LEq) is non-solvable if s > 2. 














Notice that the conditions in Theorem 2.6 is not sufficient, i.e., if GILEq] ~ Kny ing, .nes 
we can not claim that (LEq) is non-solvable or not. For example, let (LEq*) and (LEq**) be 


16 Linfan Mao 


two linear equations systems with 


1 0 0O 1 0 0 
At = 0 1 O At = 0 1 0 
1 1 0 2 2 
1 -1 0 i222 


Then G[LEq*| ~ G[LEq**| ~ K4. Clearly, the linear equation system (LEq*) is solvable with 
x1 = 0, 22 = 0 but (LEgq**) is non-solvable. We will find necessary and sufficient conditions 
for linear equation systems with two or three variables just by their combinatorial structures 
in the following sections. 

§3. Linear Equation System with 2 Variables 

Let 


AX = (b1,b2,--+ bm)? (LEq2) 


be a linear equation system in 2 variables with 


Qa11 a12 
a21 a22 XY 
A= and X= 
x2 
Am1 aAm2 


for an integer m > 2. Then Theorem 2.4 is refined in the following. 


Theorem 3.1 A linear equation system (LEq2) is non-solvable if and only if one of the following 
conditions hold: 

(1) there are integers 1 <i,j <m such that aj /aj1 = ai2/ajo 4 bi /d;; 

(2) there are integers 1 < i,j,k < m such that 


Ail Ai2 ai Oj 
Qj1 aj2 4 aj1 b; 
ail Ai2 ayy Di 
Aki AK api OK 














Proof The condition (1) is nothing but the conclusion in Corollary 2.3, i.e., the ith equation 
is parallel to the jth equation. Now if there no such parallel equations in (LEq2), let T be the 
elementary transformation replacing all other jth equations by the jth equation plus (—aj1/ai1) 


Non-Solvable Spaces of Linear Equation Systems 17 


times the ith equation for integers 1 < 7 < m. We get a transformation T(At) of At following 














ail Ai2 ain 0; 
0 

a11 412 ay by 

ail Ai2 ai by 
0 

As1 as2 As1 bs 

+) _ 
T(A )= ail ai2 b; ’ 

ail Ai2 ai Oy 
0 

at1 4t2 at be 

ail aj2 Qil bi 
0 

aml aAm2 aml bm, 


where s = i—1, ¢ =i+1. Applying Corollary 2.3 again, we know that there are integers 
1<1,9,k <m such that 


ail Qi2 ail b; 
Qj1 ajo ¥ aj1 b; 
ail Ai2 ayy bi 
Akl Ar aki br 























if the linear equation system (LEQ2) is non-solvable. 





Notice that a linear equation ax; + br2 = c with a 4 0 or b ¥ 0 is a straight line on R?. 


We get the following result. 


Theorem 3.2 A liner equation system (LEq2) is non-solvable if and only if one of conditions 
following hold: 
(1) there are integers 1 <i,j <m such that aj /aj1 = ai2/ajo 4 bi /d;; 
G11 12 


(2) let #0 and 
a21 422 


by aay ayy by 
bz az2 az, be 
0 _ 7 — 
t= ’ 2 
aii a2 aii 412 
a21 a22 a21 422 


Then there is an integer 1, 1 <i<m such that 


aj (21 — x) + aj2(X2 = re) # 0. 


18 Linfan Mao 


Proof If the linear equation system (LE q2) has a solution (x9, x9), then 


by aay ayy by 
bz a22 az bg 
0 _ Os 
y= ’ T= 
ai, a42 Qai1 412 
a21 422 a21 422 


and a2} + ai2r8 = bi, ie., ai (a1 — x?) + aio(x2 — x9) = 0 for any integers 1 <i < m. Thus, 
if the linear equation system (L£q2) is non-solvable, there must be integers 1 < i,7 <m such 
that aj1/aj1 = ai2/aj2 # b;/b;, or there is an integer 1 < i < m such that 


aji(a1 — 29) + ajo(ao — x8) £0. 











This completes the proof. 





For a non-solvable linear equation system (LE q2), there is a naturally induced intersection- 
free graph I[LEq2| by (LEq2) on the plane R? defined following: 


V(I[LEq2]) = {(27 ay )lanay + ary = bi, ajay’ + ajay =b;,1< i,j Sm}. 

E(I[LEq2]) = {(vij, via) |the segament between points (c'!, ct!) and («i!, ci!) in R?}. (where 
0 = (ae) oF) fon < 1,9 < m): 

Such an intersection-free graph is clearly a planar graph with each edge a straight segment 


since all intersection of edges appear at vertices. For example, let the linear equation system 
be (LEq2) with 


Ar = 


ee Be 
Oo NO RF Re 
EF wo wo bw 


Then its intersection-free graph I[L.Eq2] is shown in Fig.2. 


v2 
wm=l 


V14 


U45 
K 45 
U24 
1 U24 
v13 = RWG V13 = V15 = U35 





U24 





Non-Solvable Spaces of Linear Equation Systems 19 


Let H be a planar graph with each edge a straight segment on R?. Its c-line graph Lo(H) 
is defined by 


V(Lc(H)) = {straight lines L = eye2---e;,8 > 1 in A}; 

E(Lo(H)) = {(L1,L2)| if e; and e7 are adjacent in H for Li = ejej:--e7, Lg = 
efen-2-e2. Loe Sl}. 

The following result characterizes the combinatorial structure of non-solvable linear equa- 


tion systems with two variables by intersection-free graphs I[L Fq2]. 


Theorem 3.3 A linear equation system (LEq2) is non-solvable if and only if 
G[LEq2] ~ Lo(H)), 
where H is a planar graph of order |H| > 2 on R? with each edge a straight segment 


Proof Notice that there is naturally a one to one mapping ¢ : V(G|LEq2]) — V(Lo([LEq2])) 
determined by ¢(S?) = Si for integers 1 < i < m, where S? and S} denote respectively the 


solutions of equation a;12%1 +a;2%2 = b; on the plane R? or the union of points between (2}’, x3’) 
and (xi!, 2!) with 
ij tj 
Airy +4;2%y = b; 
LI a tnt d ab 
ary + aj2ry = b; 
and 


ay! + ant} = b; 





ani! + anak = by 


for integers 1 < i, j,1 < m. Now if ($?, S?) € E(G[LEgq2]), then $? (|S? 4 0. Whence, 


Si) 3} = 9(S?) ($87) = 9(5? (]S?) #0 


by definition. Thus (97,57) € Lo(I(LEq2)). By definition, ¢ is an isomorphism between 
G|LEq2] and Lco(I|LEq2]), a line graph of planar graph I[LEq2| with each edge a straight 
segment. 

Conversely, let H be a planar graph with each edge a straight segment on the plane R?. Not 
loss of generality, we assume that edges €1,2,--- ,e, € E(#) is on a straight line L with equation 
ap1%1 + Az2%2 = by. Denote all straight lines in H by @. Then H is the intersection-free graph 


of linear equation system 
Gr1%1 + ap2% =bp, LE. (LEq2*) 


Thus, 
G|LEq2*| ~ H. 














This completes the proof. 


Similarly, we can also consider the liner equation system (LEq2) with condition on x1 or 
x2 such as 


AX = (bi, be, +++ ,bm)™ (L~ Eq2) 


20 Linfan Mao 


with 
Q11 a12 
a21 a22 Ty 
A = 5 xX — 
XQ 
Am1 Am2 


and x; > x° for a real number x° and an integer m > 2. In geometry, each of there equation 
is a ray on the plane R?, seeing also references [5]-[6]. Then the following conclusion can be 
obtained like with Theorems 3.2 and 3.3. 


Theorem 3.4 A linear equation system (L~ Eq2) is non-solvable if and only if 
G[LEq2] ~ Lo(H)), 


where H is a planar graph of order |H| > 2 on R? with each edge a straight segment. 


§4. Linear Equation Systems with 3 Variables 


Let 
AX = (bi, ba,+++ 5m)” (LEq3) 
be a linear equation system in 3 variables with 


Q11 a12 a13 


a21 a22 a23 
A= and X= v2 


X3 
Gm1 Am2 m3 


for an integer m > 3. Then Theorem 2.4 is refined in the following. 


Theorem 4.1 A linear equation system (LEq3) is non-solvable if and only if one of the following 
conditions hold: 


(1) there are integers 1 < 4,9 < m such that a1 /G51 = a2 /Q;2 = 043/053 # b;/b;; 
(2) if (ai, ai2, ai3) and (aj1, aj2,4;3) are independent, then there are numbers , 1 and an 
integer 1, 1<1<m such that 


(ai1, d12, @13) = A(@i1, Gi2, G3) + W(j1, 472, 23) 
but b # Ab; + pub; ; 
(3) if (a1, Qi2, Gi3), (@j1, 472, 43) and (x1, @k2,4n3) are independent, then there are num- 
bers A, p,V and an integer 1, 1<1<m such that 
(an, ai2, a3) = A(ai1, ai2, ai3) = play, Qj2, aj3) or V (ae, Qk, aK3) 


but by x dd; + pub; + Vbp. 


Non-Solvable Spaces of Linear Equation Systems 21 


Proof By Theorem 2.1, the linear equation system (LFq3) is non-solvable if and only 
if 1 < rankA #4 rankAt < 4. Thus the non-solvable possibilities of (Z.Eq3) are respectively 
rankA = 1, 2 < rankAt < 4, rankA = 2, 3 < rankAt < 4 and rankA = 3, rankAt = 4. We 
discuss each of these cases following. 


Case 1 rankA = 1 but 2 < rankAt < 4 


In this case, all row vectors in A are dependent. Thus there exists a number 4 such that 
Ar => a1 / O51 = ai2/ G52 = 43/053 but aN x b;/;. 
Case 2 rankA = 2, 3 < rankAt <4 


In this case, there are two independent row vectors. Without loss of generality, let 
(@i1, G2, @i3) and (a;1, a2, 4;3) be such row vectors. Then there must be an integer 1, 1 <1 <m 
such that the [th row can not be the linear combination of the ith row and jth row. Whence, 
there are numbers 4, js such that 


(ai1, d12, @13) = A( Gir, Gi2, G3) + W(G;1, 472, a3) 
Case 3 rankA = 3, rankAt = 4 


In this case, there are three independent row vectors. Without loss of generality, let 
(@i1, G2, @i3), (Aj1, 4;2,4;3) and (ax1,@%2, 4x3) be such row vectors. Then there must be an 
integer 1, 1 < 1 < m such that the [th row can not be the linear combination of the ith row, 
jth row and kth row. Thus there are numbers 4, yu, v such that 


(ai1, d12, @13) = A(@i1, Gi2, G3) + W(Aj1, 472, 473) + V(Ak1, On2, Ok3) 














but b; A Abj + wb; + vby. Combining the discussion of Case 1-Case 3, the proof is complete. 


Notice that the linear equation system (LFq3) can be transformed to the following (L Fq3*) 
by elementary transformation, i.e., each jth row plus —a;3/aj3 times the ith row in (LEq3) for 
an integer i, 1 <i <m with aj 4 0, 


/ / / 1 \T * 
A'X = (b),05,--+ 01) (LEgq3*) 
with 
/ / / 
Q11 a2 0 by 
/ / / 
Ait = | i= %-1)2 0 Oy 
a >) 
ail aj2 ai3 bi 
/ / / 
Gita. %\Q+1)2 0 O44 
/ / / 
amt ama 0 Une 
where ay = 4j1 — 473041 /a13, Ajo = G2 — 4724;2/ai3 and bi = b; — aj3b;/ai3 fro integers 


1<j<™m. Applying Theorem 3.3, we get the a combinatorial characterizing on non-solvable 
linear systems (LFq3) following. 


22 Linfan Mao 


Theorem 4.2 A linear equation system (LEq3) is non-solvable if and only if G[LEq3] # Km 
or G[LEg3*| ~ u+ Lo(H), where H denotes a planar graph with order |H| > 2, sizem—1 
and each edge a straight segment, u+ G the join of vertex u with G. 


Proof By Theorem 2.4, the linear equation system (L£q3) is non-solvable if and only if 
G|LEq3] # Ky, or the linear equation system (LFq3*) is non-solvable, which implies that the 


linear equation subsystem following 
BX" = (b1,-°: 04, 0;4a- + Bee (LEq2*) 
with 
ay a> 


B= and X’= (a1, a2)" 


/ / 
Gi-1)1 %i-1)2 
al a’, 

(41)1 %i+1)2 
/ / 

mi Ame 


a 
is non-solvable. Applying Theorem 3.3, we know that the linear equation subsystem (LE q2*) 
is non-solvable if and only if G[LEq2*] ~ Lc(H)), where H is a planar graph H of size m— 1 
with each edge a straight segment. Thus the linear equation system (Lq3*) is non-solvable if 


and only if G[LEq3*] ~ u+ Lc(#). 














§5. Linear Homeomorphisms Equations 


A homeomorphism on R” is a continuous 1 — 1 mapping h : R” > R” such that its inverse h7! 
is also continuous for an integer n > 1. There are indeed many such homeomorphisms on R”. 
For example, the linear transformations T on R”. A linear homeomorphisms equation system 


is such an equation system 


AX = (b1,b2,+++ , bm)” (L’ Eq) 
with X = (h(x1), h(x2),--- ,h(an))", where h is a homeomorphism and 
a1 412 Gin 
Ae a21 422 Gan 
die Cea fee's Mies 


for integers m, n > 1. Notice that the linear homeomorphism equation system 


ayth(x1) + ajgh(a2) +--+ dinh(an) = bi, 
aj1h(a1) mi @52(£2) abirais ajnh(an) = b; 





is solvable if and only if the linear equation system 


Qji1L1 + AQ%2 + +++ AinTn = bi, 


5121 + Aj2%Q +++ AjnTn = b; 


Non-Solvable Spaces of Linear Equation Systems 23 


is solvable. Similarly, two linear homeomorphism equations are said parallel if they are non- 
solvable. Applying Theorems 2.6, 3.3,4.2, we know the following result for linear homeomor- 
phism equation systems (L’ Eq). 


Theorem 5.1 Let (L’Eq) be a linear homeomorphism equation system for integers m,n > 1. 
Then 


(1) G[LEq) © Kny.no-n, with ny +n+2+---+ns =m, where GP is the parallel family 
with n; = |6)| for integers 1 <i <8 in (L"Egq) and (L" Eq) is non-solvable if s > 2; 

(2) Ifn = 2, (L"Eq) is non-solvable if and only if G[L"Eq ~ Lc(H)), where H is a 
planar graph of order |H| > 2 on R? with each edge a homeomorphism of straight segment, and 
if n = 3, (L"Egq) is non-solvable if and only if G[L’Eq| #4 Km or G[LEq3*] ~ ut+ Lo(H), 
where H denotes a planar graph with order |H| > 2, size m—1 and each edge a homeomorphism 


of straight segment. 


References 


1] R.Abraham, J.E.Marsden and T.Ratiu, Manifolds, Tensors Analysis and Applications, 
Addison-Wesley Publishing Company, Inc., 1983. 

2] G.Birkhoff and S.MacLane, A Survey of Modern Algebra (4th edition), Macmillan Publish- 
ing Co., Inc, 1977. 

3] K.Hoffman and R.Kunze, Linear Algebra (2th edition), Prentice-Hall, Inc., Englewood 
Cliffs, New Jersey, 1971. 

4] L.Kuciuk and M.Antholy, An Introduction to Smarandache Geometries, JP Journal of 
Geometry and Topology, 5(1), 2005,77-81. 

5] Linfan Mao, Parallel bundles in planar map geometries, Scientia Magna, Vol.1(2005), No.2, 
120-133. 

6] Linfan Mao, On multi-metric spaces, Scientia Magna, Vol.2,No.1(2006), 87-94. 

7| Linfan Mao, Euclidean pseudo-geometry on R”, International J.Math. Combin., Vol.1 
(2009), 90-95. 

8] Linfan Mao, Automorphism Groups of Maps, Surfaces and Smarandache Geometries (Sec- 
ond edition), Graduate Textbook in Mathematics, The Education Publisher Inc. 2011. 

9] Linfan Mao, Smarandache Multi-Space Theory (Second edition), Graduate Textbook in 
Mathematics, The Education Publisher Inc. 2011. 

[10] Linfan Mao, Combinatorial Geometry with Applications to Field Theory (Second edition), 
Graduate Textbook in Mathematics, The Education Publisher Inc. 2011. 

[11] W.S.Massey, Algebraic Topology: An Introduction, Springer-Verlag, New York, etc., 1977. 
[12] F.Smarandache, Mixed noneuclidean geometries, Eprint arXiv: math/0010119, 10/2000. 
[13] F.Smarandache, A Unifying Field in Logics—Neutrosopy: Neturosophic Probability, Set, 








and Logic, American research Press, Rehoboth, 1999. 


Math. Combin. Book Ser. Vol.2(2012), 24-31 


Roman Domination in Complementary Prism Graphs 


B.Chaluvaraju and V.Chaitra 


1(Department of Mathematics, Bangalore University, Central College Campus, Bangalore -560 001, India) 


E-mail: bchaluvaraju@gmail.com, chaitrashok@gmail.com 


Abstract: A Roman domination function on a complementary prism graph GG® is a 
function f : VUV* — {0,1,2} such that every vertex with label 0 has a neighbor with 
label 2. The Roman domination number yr(GG*) of a graph G = (V, £) is the minimum 
of SS. evuved (a) over such functions, where the complementary prism GG*° of G is graph 
obtained from disjoint union of G and its complement G° by adding edges of a perfect 
matching between corresponding vertices of G and G°. In this paper, we have investigated 


few properties of yr(GG*) and its relation with other parameters are obtained. 


Key Words: Graph, domination number, Roman domination number, Smarandachely 
Roman s-domination function, complementary prism, Roman domination of complementary 


prism. 


AMS(2010): 05C69, 05070 


§1. Introduction 


In this paper, G is a simple graph with vertex set V(G) and edge set E(G). Let n = |V| and 
m = |E| denote the number of vertices and edges of a graph G, respectively. For any vertex v 
of G, let N(v) and N|v] denote its open and closed neighborhoods respectively. ag(G)(ai1(G)), 
is the minimum number of vertices (edges) in a vertex (edge) cover of G. G9(G)(Gi(G)), is the 
minimum number of vertices (edges) in a maximal independent set of vertex (edge) of G. Let 
deg(v) be the degree of vertex v in G. Then A(G) and 6(G) be maximum and minimum degree 
of G, respectively. If M is a matching in a graph G with the property that every vertex of G is 
incident with an edge of M, then M is a perfect matching in G. The complement G° of a graph 
G is the graph having the same set of vertices as G denoted by V° and in which two vertices 
are adjacent, if and only if they are not adjacent in G. Refer to [5] for additional graph theory 
terminology. 

A dominating set D C V for a graph G is such that each v € V is either in D or adjacent 
to a vertex of D. The domination number 7(G) is the minimum cardinality of a dominating 
set of G. Further, a dominating set D is a minimal dominating set of G, if and only if for each 
vertex v € D, D—v is not a dominating set of G. For complete review on theory of domination 


1Received April 8, 2012. Accepted June 8, 2012. 


Roman Domination in Complementary Prism Graphs 25 


and its related parameters, we refer [1], [6]and [7]. 

For a graph G = (V, £), let f : V — {0,1,2} and let (Vo, Vi, V2) be the ordered partition 
of V induced by f, where V; = {v € V/f(v) =i} and |V;| = n; for 7 = 0,1,2. There exist 1-1 
correspondence between the functions f : V > {0,1,2} and the ordered partitions (Vo, Vi, V2) 
of V. Thus we write f = (Vo, Vi, V2). 

A function f = (Vo,Vi, V2) is a Roman dominating function (RDF) if V2 > Vo, where > 
signifies that the set V2 dominates the set Vo. The weight of a Roman dominating function 
is the value f(V) = \O,-y f(v) = 2|V2| + |Vi]. Roman dominating number yr(G), equals the 
minimum weight of an RDF of G, we say that a function f = (Vo,Vi, V2) is a yr-function 
if it is an RDF and f(V) = yr(G). Generally, let J Cc {0,1,2,---,n}. A Smarandachely 
Roman s-dominating function for an integer s, 2 << s <n ona graph G = (V,E) is a function 
f:V — {0,1,2,---,n} satisfying the condition that |f(w) — f(v)| > s for each edge wv € E 
with f(u) or f(v) € I. Particularly, if we choose n = s = 2 and I = {0}, such a Smarandachely 
Roman s-dominating function is nothing but the Roman domination function. For more details 
on Roman dominations and its related parameters we refer [3]-[4] and [9]-[11]. 

In [8], Haynes etal., introduced the concept of domination and total domination in com- 
plementary prisms. Analogously, we initiate the Roman domination in complementary prism 
as follows: 

A Roman domination function on a complementary prism graph GG* is a function f : 
VUV* = {0,1, 2} such that every vertex with label 0 has a neighbor with label 2. The Roman 
domination number yr(GG°) of a graph G = (V, £) is the minimum of }).eyyye f(#) over such 
functions, where the complementary prism GG* of G is graph obtained from disjoint union of G 
and its complement G° by adding edges of a perfect matching between corresponding vertices 
of G and G°. 


§2. Results 


We begin by making a couple of observations. 
Observation 2.1 For any graph G with order n and size m, 
m(GG*) = n(n + 1)/2. 
Observation 2.2 For any graph G, 
(i) 61(GG°) =n. 
(ii) a1(GG*) + Bi(GG*) = 2n. 


Proof Let G be a graph and GG* be its complementary prism graph with perfect matching 
M. If one to one correspondence between vertices of a graph G and its complement G° in GG*, 
then GG* has even order and M is a 1-regular spanning sub graph of GG‘°, thus (i) follows and 
due to the fact of ai(G) + 31(G) = n,(ii) follows. 














26 B.Chaluvaraju and V.Chaitra 


Observation 2.3 For any graph G, 
V(GG*) =n 
if and only if G or G° is totally disconnected graph. 


Proof Let there be n vertices of degree 1 in GG*. Let D be a dominating set of GG* and 
v be a vertex of G of degree n —1, v € D. In GG*, v dominates n vertices and remaining n — 1 
vertices are pendent vertices which has to dominate itself. Hence y(GG°) = n. Conversely, if 











7(GG°) =n, then there are n vertices in minimal dominating set D. 





Theorem 2.1 For any graph G, 
yr(GG*) = a1(GG*) + B1(GG*) 
if and only if G being an isolated vertex. 


Proof If G is an isolated vertex, then GG‘ is Ky and yr(GG*) = 2,a,(GG*) = 1 and 
Gi(GG*) = 1. Conversely, if yr(GG°) = ai(GG*) + 61(GG*). By above observation, then we 
have yr(GG*) = 2|V2| + |Vil. Thus we consider the following cases: 


Case 1 If V2 = ¢,|Vi| = 2, then Vo = ¢ and GG* & Ky. 
Case 2 If |V2| =1,|Vi| = ¢, then GG* is a complete graph. 











Hence the result follows. 





Theorem 2.2 Let G and G° be two complete graphs then GG® is also complete if and only if 
G= kK. 


Proof If G = k, then G° = ky, and GG° = K2 which is a complete graph. Conversely, if 
GG* is complete graph then any vertex v of G is adjacent to n — 1 vertices of G and n vertices 
of G°. According to definition of complementary prism this is not possible for graph other than 
Ky. 














Theorem 2.3 For any graph G, 
V(GG*) < yr(GG*) < 27(GG*). 
Further,the upper bound is attained if Vi(GG*) = ¢. 


Proof Let f = (Vo, Vi, V2) be yr-function. If V2 > Vo and (Vi U V2) dominates GG*, then 
(GG) < |Vi U Val = |Vi| + 2|Vo| = yr(GG*). Thus the result follows. 

Let f = (Vo,Vi, V2) be an RDF of GG*° with |D| = 7(GG*). Let V2 = D,V, = ¢ and 
VY =V-—D. Since f is an RDF and yr(GG*) denotes minimum weight of f(V). It follows 
yR(GG*) < f(V) = |Vi| + 2|Va| = 2|S| = 27(GG*). Hence the upper bound follows. For graph 
GG*, let v be vertex not in Vj, implies that either v € V2 or v € Yo. If vu € V2 then v € D, 
yrR(GGS) = 2|Vo| + |Vi| = 2|D| = 27(GG*). If vu € Y then N(v) C Va or N(v) C Vo as v does 
not belong to V;. Hence the result. 














Roman Domination in Complementary Prism Graphs 27 


Theorem 2.4 For any graph G, 
2 < yr(GG*) < (n+ 1). 


Further, the lower bound is attained if and only if G = Ky, and the upper bound is attained if 
G or G® is totally disconnected graph. 


Proof Let G be a graph with n > 1. If f = {Vo,Vi, Vo} be a RDF of GG*, then 
yr(GG°) > 2. Thus the lower bound follows. 

Upper bound is proved by using mathematical induction on number of vertices of G. For 
n=1, GG° = Ko, 7rR(GG°) =n+1. For n = 2, GG° = Py, yr(GG*) = n+1. Assume the 
result to be true for some graph H with n — 1 vertices, yr(HH‘°) < n. Let G be a graph 
obtained by adding a vertex v to H. If v is adjacent to a vertex w in H which belongs to 
V2, then v € Vo, yrR(GG°) =n < n-+1. If v is adjacent to a vertex either in Vo or Vi, then 
yr(GG°) =n-+1. If v is adjacent to all vertices of H then yr(GG°) <n <n+1. Hence upper 
bound follows for any number of vertices of G. 

Now, we prove the second part. If G © Ky, then yr(GG*°) = 2. On the other hand, if 
yrR(GG°) = 2 = 2|V2| + |Vi| then we have following cases: 


Case 1 If |V2| = 1,|Vil = 0, then there exist a vertex v € V(GG°) such that degree of 
v = (n— 1), thus one and only graph with this property is GGS & Ka. Hence G = Ky. 


Case 2 If |V2| = 0,|Vi| = 2, then there are only two vertices in the GG° which are connected 
by an edge. Hence the result. 


If G is totally disconnected then G‘° is a complete graph. Any vertex v° in G° dominates 











n vertices in GG°. Remaining n — 1 vertices of GG® are in V,. Hence yr(GG*) =n +1. 





Proposition 2.1([3]) For any path P, and cycle Cy, with n > 3 vertices, 
yR(Pn) = Ya(Cn) = [2n/3], 
where [a] is the smallest integer not less than x. 
Theorem 2.5 For any graph G, 
(i) of G=P, with n > 3 vertices, then 
YR(GG*) = 4+ [2(n — 3)/3]; 
(it) if G=C, with n> 4 vertices, then 


yR(GG°) = 4+4 [2(n — 2)/3]. 


Proof (i) Let G = P, be a path with with n > 3 vertices. Then we have the following 


cases: 


Case 1 Let f = (Vo,Vi, V2) be an RDF and a pendent vertex v is adjacent to a vertex wu in 
G. The vertex v° is not adjacent to a vertex u° in V°. But the vertex of v° in V° is adjacent 


28 B.Chaluvaraju and V.Chaitra 


to n vertices of GG°. Let v° € V2 and N(v°) C Vo. There are n vertices left and u° € N[u] but 
{N(u°) — u} C Vo. Hence u € Vo, N(u) C Vo. There are (n — 3) vertices left, whose induced 
subgraph H forms a path with yr(H) = [2(n—3)/3], this implies that yr(G) = 4+[2(n—3)/3]. 


Case 2 If v is not a pendent vertex, let it be adjacent to vertices u and w in G. Repeating 
same procedure as above case , yr(GG°) = 6 + [2(n — 3)/3], which is a contradiction to fact of 
RDF. 


(it) Let G=C,, be acycle with n > 4 vertices. Let f = (Vo, Vi, V2) be an RDF and w be 
a vertex adjacent to vertex u and v in G, and w° is not adjacent to u° and v° in V°. But w° is 
adjacent to (n — 2) vertices of GG°. Let w° € V2 and N(w°) C Vo. There are (n + 1)-vertices 
left with u° or v° € V2. With out loss of generality, let uc € V2, N(u°) C Vo. There are 
(n — 2) vertices left, whose induced subgraph H forms a path with yr(H) = [2(n — 2)/3] and 
V2 = {w, u°}, this implies that yr(G) = 4+ [2(n — 2)/3]. 














Theorem 2.6 For any graph G, 


maz{yr(G),yR(G*)} < yrR(GG*) < (yR(G) + yR(G*)). 
Further, the upper bound is attained if and only if the graph G is isomorphic with Ky. 


Proof Let G be a graph and let f : V — {0,1,2} and f = (Vo, Vi, V2) be RDF. Since GG* 
has 2n vertices when G has n vertices, hence max{yr(G), yr(G°)} < yr(GG*) follows. 

For any graph G with n > 1 vertices. By Theorem 2.4, we have yr(GG°) < (n+ 1) and 
(yr (G) + yrR(G*)) < (n+ 2) = (n+ 1) +1. Hence the upper bound follows. 

Let G = ky. Then GG* = Ko, thus the upper bound is attained. Conversely, suppose 
G & ky. Let u and v be two adjacent vertices in G and u is adjacent to v and u° in GG*. 
The set {u,v°} is a dominating set out of which u € V2,u° € Vi. yr(G) = 2, yrR(G°) = 0 and 
yr(GG°) = 3 which is a contradiction. Hence no two vertices are adjacent in G. 














Theorem 2.7 If degree of every vertex of a graph G is one less than number of vertices of G, 
then 
yr(GG*) = 7(GG*) +1. 


Proof Let f = (Vo,Vi, V2) be an RDF and let v be a vertex of G of degree n — 1. In 
GG°,v is adjacent to n vertices. If D is a minimum dominating set of GG*° then v € D, 
v € V2 also N(v) C Vo. Remaining n — 1 belongs to V; and D. |D| = 7(GG°) = n and 
yrR(GG°) =n+1=7(GG*) +1. 














Theorem 2.8 For any graph G with n > 1 vertices, 
yR(GG*) < [2n — (A(GG*) + 1)]. 
Further, the bound is attained if G is a complete graph. 


Proof Let G be any graph with n > 1 vertices. Then GG has 2n- vertices. Let f = 
(Vo, Vi, V2) be an RDF and v be any vertex of GG such that deg(v) = A(GG*). Then v 


Roman Domination in Complementary Prism Graphs 29 


dominates A(GG°) + 1 vertices. Let v € V2 andN(v) C Vo. There are (2n — (A(GG*) + 1) 
vertices left in GG*, which belongs to one of Vo, Vi or V2. If all these vertices € Vi, then 
YR(GG*) = 2|Va| + [Vil = 2 + (2n — A(GG*) + 1) = 2n — A(GG*) + 1. Hence lower bound is 
attained when G = K,,, where v is a vertex of G. If not all remaining vertices belong to Vi, 
then there may be vertices belonging to V2 and which implies there neighbors belong to Vo. 











Hence the result follows. 





Theorem 2.9 For any graph G, 
YR(GG*)° < yR(GG*). 


Further, the bound is attained for one of the following conditions: 


(i) GG° = (GG); 
(it) GG®* is a complete graph. 


Proof Let G be a graph, GG* be its complementary graph and (GG‘°)° be complement 
of complementary prism. According to definition of GG there should be one to one matching 
between vertices of G and G°, where as in (GG°)° there will be one to (n—1) matching between 
vertices of G and G° implies that adjacency of vertices will be more in (GG°)°. Hence the result. 
If GG° = (GG°)°, domination and Roman domination of these two graphs are same. The only 
complete graph GG® can be is Ko. (GG*)° will be two isolated vertices, yp(GG*°) = 2 and 
yr(GG°)° = 2. Hence bound is attained. 














To prove our next results, we make use of following definitions: 


A rooted tree is a tree with a countable number of vertices, in which a particular vertex is 
distinguished from the others and called the root. In a rooted tree, the parent of a vertex is 
the vertex connected to it on the path to the root; every vertex except the root has a unique 
parent. A child of a vertex v is a vertex of which v is the parent. A leaf is a vertex without 
children. 


A graph with exactly one induced cycle is called unicyclic. 
Theorem 2.10 For any rooted tree T, 
yR(TT*) = 2|S2| + [Si], 
where 5S; C Vi and Sz C Vo. 


Proof Let T be a rooted tree and f = (Vo, Vi, V2) be RDF of a complementary prism TT*. 
We label all parent vertices of T as P,, Po, ....P, where P; is root of a tree T’. Let S, be set of all 
parent vertices of TJ’, S; be set of all leaf vertices of T and v € S; be a vertex farthest from Py. 
The vertex v° is adjacent to (n — 1)—vertices in TT. Let v° € Sz, and N(v°) C Vo. Let Py be 
parent vertex of vu € T. For i=1 to k if P; is not assigned weight then P; € S: and N(P;) C Vo. 
If P; is assigned weight and check its leaf vertices in T, then we consider the following cases: 


Case 1 If P; has at least 2 leaf vertices, then P; € Sz and N(P;) C VW. 


30 B.Chaluvaraju and V.Chaitra 


Case 2 If P; has at most 1 leaf vertex, then all such leaf vertices belong to S,. Thus yr(GG*) = 
2|.S2| + |.S1| follows. 














Theorem 2.11 Let G° be a complement of a graph G. Then the complementary prism GG° is 
(i) isomorphic with a tree T if and only if G or G° has at most two vertices. 
(ii) (n+ 1)/2-regular graph if and only if G is (n — 1)/2-regular. 


(itt) unicyclic graph if and only if G has exactly 3 vertices. 


Proof (i) Suppose GG® is a tree T with the graph G having minimum three vertices. 
Then we have the following cases: 


Case 1 Let u, v and w be vertices of G with v is adjacent to both u and w. In GG*°, u® is 
connected to u and w* also v° is connected to v. Hence there is a closed path u-v-w-w*-u°-u, 


which is a contradicting to our assumption. 


Case 2 If vertices u, v and w are totally disconnected in G, then G° is a complete graph. Since 
every complete graph G with n > 3 has cycle. Hence GG* is not a tree. 


Case 3 If u and v are adjacent but which is not adjacent to w in G, then in GG* there is a 
closed path u-u°-w%-v°-v°-u, again which is a contradicting to assumption. 

On the other hand, if G has one vertex, then GG*° = Kz and if G have two vertices, then 
GG° = P,. In both the cases GG‘* is a tree. 


(it) Let G be r-regular graph, where r = (n — 1)/2, then G° is nm —r —1 regular. In 
GG, degree of every vertex in G is r+ 1 = (n+ 1)/2 and degree of every vertex in G° 
isn —r = (n+ 1)/2, which implies GG° is (n + 1)/2-regular. Conversely, suppose GG° is 
s = (n+1)/2-regular. Let EF be set of all edges making perfect match between G and G°. In 
GG — E, G is s—1-regular and G*° is (n—s—1)-regular. Hence the graph G is (n—1)/2-regular. 


(iti) If GG has at most two vertices, then from (i), GG® is a tree. Minimum vertices 
required for a graph to be unicyclic is 3. Because of perfect matching in complementary prism 











and G and G* are connected if there are more than 3 vertices there will be more than 1 cycle. 





Acknowledgement 


Thanks are due to Prof. N. D Soner for his help and valuable suggestions in the preparation of 
this paper. 


References 


[1] B.D.Acharya, H.B.Walikar and E.Sampathkumar, Recent developments in the theory of 
domination in graphs, MRI Lecture Notes in Math., 1 (1979), Mehta Research Institute, 
Alahabad. 








Roman Domination in Complementary Prism Graphs 31 


B.Chaluvaraju and V.Chaitra, Roman domination in odd and even graph, South East 
Asian Journal of Mathematics and Mathematical Science (to appear). 

E.J.Cockayne, P.A.Dreyer Jr, S.M.Hedetniemi and $.T.Hedetniemi, Roman domination in 
graphs, Discrete Mathematics, 278 (2004) 11-24. 

O.Favaron, H.Karamic, R.Khoeilar and $.M.Sheikholeslami, Note on the Roman domina- 
tion number of a graph, Discrete Mathematics, 309 (2009) 3447-3451. 

F.Harary, Graph theory, Addison-Wesley, Reading Mass (1969). 

T.W.Haynes, S.T.Hedetniemi and P.J.Slater, Fundamentals of domination in graphs, Mar- 
cel Dekker, Inc., New York (1998). 

T.W.Haynes, S.T.Hedetniemi and P.J.Slater, Domination in graphs: Advanced topics, Mar- 
cel Dekker, Inc., New York (1998). 

T.W.Haynes, M.A.Henning and L.C. van der Merwe, Domination and total domination in 
complementary prisms, Journal of Combinatorial Optimization,18 (1)(2009) 23-37. 

Nader Jafari Rad, Lutz Volkmann, Roman domination perfect graphs, An.st. Univ ovidius 
constanta., 19(3)(2011)167-174. 

L.Stewart, Defend the Roman Empire, Sci. Amer., 281(6)(1999)136-139. 

N.D.Soner, B.Chaluvaraju and J.P.Srivatsava, Roman edge domination in graphs, Proc. 
Nat. Acad. Sci. India. Sect. A, Vol.79 (2009) 45-50. 


Math. Combin. Book Ser. Vol.2(2012), 82-88 


Enumeration of Rooted Nearly 2-Regualr Simple Planar Maps 


Shude Long 


Department of Mathematics, Chongqing University of Arts and Sciences, Chongqing 402160, P.R.China 


Junliang Cai 
School of Mathematical Sciences, Beijing Normal University, Beijing 100875, P.R.China 
E-mail: longshude@163.com; caijunliang@bnu.edu.cn 


Abstract: This paper discusses the enumeration of rooted nearly 2-regular simple planar 
maps and presents some formulae for such maps with the valency of the root-face, the 


numbers of nonrooted vertices and inner faces as three parameters. 


Key Words: Smarandachely map, simple map, nearly 2-regular map, enumerating func- 


tion, functional equation, Lagrangian inversion, Lagrangian inversion. 


AMS(2010): 05C45, 05C30 


§1. Introduction 


Let S be a surface. For an integer k > 0, a Smarandachely k-map on S is such a pseudo-map on 
S just with & faces that not being 2-cell. If k = 0, such a Smarandachely map is called map. In 
the field of enumerating planar maps, many functional equations for a variety of sets of planar 
maps have been found and some solutions of the equations are obtained. Some nice skills are 
applied in this area and they have set up the foundation of enumerative theory [2], [5], [6] and 
[9-13]. But the discussion on enumerating function of simple planar maps is very few. All the 
results obtained so far are almost concentrated in general simple planar maps [3], [4], [7] and 





[8]. In 1997, Cai [1] investigated for the first time the enumeration of simple Eulerian planar 
maps with the valency of root-vertex, the number of inner edges and the valency of root-face as 
parameters and a functional equation satisfied by its enumerating function was obtained, but 
it is very complicated and its solution has not been found up to now. 

In this paper we treat the enumeration of rooted nearly 2-regular simple planar maps 
with the valency of the root-face, the numbers of nonrooted vertices and inner faces as three 
parameters. Several explicit expressions of its enumerating functions are obtained and one of 
them is summation-free. 

Now, we define some basic concepts and terms. In general, rooting a map means distin- 
guishing one edge on the boundary of the outer face as the root-edge, and one end of that edge 
as the root-vertex. In diagrams we usually represent the root-edge as an edge with an arrow on 


1Supported by the NNSFC under Grant No. 10271017 and Chongqing Municipal Education Commission 


under Grant No. KJ101204. 
2Received February 24, 2012. Accepted June 10, 2012. 


Enumeration of Rooted Nearly 2-Regualr Simple Planar Maps 33 


the outer face, the arrow being drawn from the root-vertex to the other end. So the outer face 
is also called the root-face. A planar map with a rooting is said to be a rooted planar map. We 
say that two rooted planar maps are combinatorially equivalent or up to root-preserving iso- 
morphism if they are related by 1-1 correspondence of their elements, which maps vertices onto 
vertices, edges onto edges and faces onto faces, which preserves incidence relations and which 
preserves the root-vertex, root-edge and root-face. Otherwise, combinatorially inequivalent or 
nonisomorphic here. 

A nearly 2-regular map is a rooted map such that all vertices probably except the root- 
vertex are of valency 2. A map is said to be simple, if there is neither loop nor parallel edge. 

For a set of some maps .@, the enumerating function discussed in this paper is defined as 


faa = So) eer geo, (1) 
Meu 


where [(M),p(M) and q(M) are the root-face valency, the number of nonrooted vertices and 
the number of inner faces of M/, respectively. 


Furthermore, we introduce some other enumerating functions for .@ as follows: 


iaey) = ag, 


MEA 

hdd2= yea, 
MEA 

Hay) = oy", (2) 
MEA 


where 1(M), p(M) and q(M) are the same in (1) and n(M) is the number of edges of M, that 


is 


g.a(@,y) =fxu(@,y,Y), hay, 2) = fay, ca 
Hay) =9.a(1.y) =hayy) = fay, y)- (3) 


For the power series f(z), f(x,y) and f(x,y, z), we employ the following notations: 


OP f(a), OP) F(e,y) and a? f(x,y, z) 


to represent the coefficients of z” in f(a), xy? in f(x,y) and xy? z? in f(a, y, z), respectively. 
Terminologies and notations not explained here can be found in [11]. 


§2. Functional Equations 


In this section we will set up the functional equations satisfied by the enumerating functions 
for rooted nearly 2-regular simple planar maps. 

Let & be the set of all rooted nearly 2-regular simple planar maps with convention that 
the vertex map V is in & for convenience. From the definition of a nearly 2-regular simple map, 
for any M € &—%, each edge of M is contained in only one circuit. The circuit containing the 
root-edge is called the root circuit of M, and denoted by C(M). 


34 Shude Long and Junliang Cai 


It is clear that the length of the root circuit is no more than the root-face valency, and 


E=H+U&, (4) 
i>3 
where 
& ={M|M € @,the length of C(M) is i} (5) 


and & is only consist of the vertex map V. 
It is easy to see that the enumerating function of é is 


fe(2,y,2) = 1. (6) 


For any M € 6;(i > 3), the root circuit divides M — C(M) into two domains, the inner 
domain and outer domain. The submap of M in the outer domain is a general map in &, while 
the submap of M in the inner domain does not contribute the valency of the root-face of M. 
Therefore, the enumerating function of &; is 


fe(a,y,2) = ay 2hf, (7) 
where h = he(y,z) = fe(1,y, z). 


Theorem 2.1 The enumerating function f = fe(x,y,z) satisfies the following equation: 


= xy? zh a: 
r= 1-7 ®) 





where h = he(y, z) = fey, @). 


Proof By (4), (6) and (7), we have 





f=lt+ . gy’ tzhf 
i>3 
= vy? zhf 
- l—ay’ 











which is equivalent to the theorem. 





Let y = z in (8). Then we have 


Corollary 2.1 The enumerating function g = ge(x,y) satisfies the following equation: 





where H = He(y) = ge(1,y). 
Let x = 1 in (8). Then we obtain 


Corollary 2.2 The enumerating function h = he(y, z) satisfies the following equation: 


y’zh? —(1—y)h-y+1=0. (10) 


Enumeration of Rooted Nearly 2-Regualr Simple Planar Maps 35 


Further, let y = z in (10). Then we have 
Corollary 2.3 The enumerating function H = Hg(y) satisfies the following equation: 


yH? —-(1-y)H —y+1=0. (11) 





§3. Enumeration 


In this section we will find the explicit formulae for enumerating functions f = fe(x,y,z),g = 
ge(x,y),h = he(y,z) and H = He(y) by using Lagrangian inversion. 
By (10) we have 





Let 


yz = (1 — On). (13) 








h= Ta (14) 
By (13) and (14), we have the following parametric expression of h = he(y, z): 
0 

Y=Typ gp yea nll — On), 

h=- : i (15) 
and from which we get 
lL = 

Aen) 1-2 seer 


Theorem 3.1 The enumerating function h = he(y,z) has the following explicit expression: 


3] 
2q)\(p — q — 1)! 
he 14 00 ag Piette ae ol 


Proof By employing Lagrangian inversion with two parameters, from (15) and (16) one 


36 Shude Long and Junliang Cai 


may find that 


= (p,q) (1 + 8)P7*(1 = 26n) 
he(y, z) = = on ane 











eae 
(1+ 6)?-9-1(1 — 26n) 
= > ae ee 
e ag_90 t+ OFT =1,q-1) (1+ )P >t 
Ee = one On) anya 
>>) 3 ea 
mee i@ 
a\( —1)! 
(p—4 
=1+ y? 24, 
Sha lq ie 2q)\(q — 1)! 


which is just the theorem. 


In what follows we present a corollary of Theorem 3.1. 


y? zt 














Corollary 3.1 The enumerating eee H = He(y) has the following explicit expression: 


(n — 2q—1)! n 
0) =D ety 





Proof It follows immediately from (17) by putting x = y andn=p+4q. 


Now, let 
se cle) 
~ 14800 
By substituting (15) and (19) into Equ. (8), one may find that 
1 
= 1 — Sono ° 
1+€0 


(18) 














(19) 


(20) 


By (15), (19) and (20), we have the parametric expression of the function f = fe(x, y, z) 


as follows: 
_€(1 +8) oa OE 
Seep eg? 
1 
yz=n(l—On), f= | _ Sono” 
(1+€6)? 
According to (21), we have 
a 0 
et ps : 7 1 —26n 
Gn) a > ~ (1+ €0)(1+0)(1 — 6)" 
0 * — 





1-0n 


(21) 


(22) 


37 


Enumeration of Rooted Nearly 2-Regualr Simple Planar Maps 


Theorem 3.2 The enumerating function f = fe(x,y,z) has the following explicit expression: 


(Ee) 


LJ p+q min{| 51,4} 


ap DS) eS 


p22 q=1 Il=3 k=max{1,[424-2]} 


—q—-1l+2k-1 
a ot )atvret 


p—2q—1+3k 
Proof By using Lagrangian inversion with three variables, from (21) and (22) one may find 
that 


(2g—k—1)!k 
(q—k)!q! 


1—-2k-1 


fe(a, y, z | — 3k 


(23) 


Sa ‘(1 +0)P 4 (1 = 260) 


(x,y,z oe oF al yet a x4 
l,p,q>0 (1 ae On)a+1 i = Se 
=> alten aq) (1 + €0)' (1 + 0)? 41 (1 — 26m) alyP24 
Gee +1 €20n (140)? 
l,p>0 q=0 (1 — 0n)2 1- oe 


min{ [$1], } =) 
P—-G4d iT Te (1+ 0)! 2k-1 


a+ey d 


l,p>1 q=1 
x (1 ene Se 
min{|$J,q} 


a4yy Dy 


l,p>1q=1 p= max({0, pits 


%¢,6,n) (1 — @n)at1 


— 20n)a!yP 24 


( 


[—-2k-1 
l— 3k 
1} 





a _py (1+ 0)? 42k 1 (1 — 26 
sé a. 14+2k,q ky ( +8) ( D ly? 24 


min{|$],q} 


Cony 




















[—2k-1 
= 2 > a ( |— 3k ) 
l,p>1 q= Lp max{0,[ +=? ]} 
(0 on a = On)Ttt 
(p—q L+2k—1,q—k—1) (1 + 0)P- 94 2k1 Pate 
ae Gd —-op) vy’ z 
| p+q min{| 4] ah 
(Qqg—k—1)!k (l-2k-1 
p22 q=1 I=3 p= max{1,[4 b2q— L42q—p yy 
x ee a a 1 aly? x4 
J p+qa min{(4] ah 
(Q9g—k—1)!k (l—2k-1 
p>2 q=1 1=3 p= max{1, pit2a=—p i P}} 
p—q—1l+2k—-1 alyP2!, 
p—2q—1+ 3k 


which is what we wanted. 


Finally, we give a corollary of Theorem 3.2. 














38 


Shude Long and Junliang Cai 


Corollary 3.2 The enumerating function g = ge(x,y) has the following explicit expression: 


n LB) min{|$1,q} 


2qg—k- lk (l-2k-1 
ge(t,y) =1+ > aera 13k ) 


n>3 l=3 q=1 k=max{1,[434-"}} 


nm—2q—l+2k—-1)\ , 
m 24 
( n—3q—-1+3k jay 28) 














Proof It follows soon from (23) by putting « = y andn=p+q. 


References 


1 








Junliang Cai and Yanpei Liu, A functional equation for enumerating simple Eulerian planar 
maps, J. Northern Jiaotong Univ., 21 (1997), 554-564. 

Yanpei Liu, A note on the number of loopless Eulerian planar maps, J. Math. Res. Expos., 
(12) 1992, 165-169. 

Yanpei Liu, Enumerating rooted simple planar maps, Acta. Math. Appl. Sinica (Eng. 
Ser.), 2 (1985), 101-111. 


4] Yanpei Liu, The enumeration of simple planar maps, Utilitas Math., 34 (1988), 97-104. 
5] Yanpei Liu, Enumerating rooted loopless planar maps, Acta Math. Appl. Sinica (Eng. 


Ser.), 2 (1985), 14-26. 

Yanpei Liu, On functional equations arising from map enumerations, Discrete Math., 123 
(1993), 93-129. 

Yanpei Liu, An enumerating equation of simple planar maps with face partition (in Chi- 
nese), Acta Math. Appl. Sinica, 12(1989), 292-295. 

Yanpei Liu, On the enumeration of simple planar maps (in Chinese), Acta Math. Sinica, 
31(1988), 279-282. 

Yanpei Liu, Functional equation for enumerating loopless Eulerian maps with vertex par- 
tition (in Chinese), Kerue Tongbao, 35(1990), 1041-1044. 

Yanpei Liu, On enumerating equation of planar maps (in Chinese), Adv. Math. (China), 
18 (1989), 446-460. 

Yanpei Liu, Enumerative Theory of Maps, Kluwer, Boston, 1999. 

W.T.Tutte, A census of planar maps, Canad. J. Math., 15 (1963), 249-271. 

W.T.Tutte, A census of slicing, Canad. J. Math., 14 (1962), 705-722. 


Math. Combin. Book Ser. Vol.2(2012), 89-51 


On Pathos Total Semitotal 
and Entire Total Block Graph of a Tree 


Muddebihal M. H. 


(Department of Mathematics, Gulbarga University, Gulbarga, India) 


Syed Babajan 





(Department of Mathematics, Ghousia College of Engineering, Ramanagaram, India) 


E-mail: babajan.ghousia@gmail.com 


Abstract: In this communication, the concept of pathos total semitotal and entire total 
block graph of a tree is introduced. Its study is concentrated only on trees. We present 
a characterization of graphs whose pathos total semitotal block graphs are planar, maxi- 
mal outerplanar, minimally nonouterplanar, nonminimally nonouterplanar, noneulerian and 
hamiltonian. Also, we present a characterization of those graphs whose pathos entire to- 
tal block graphs are planar, maximal outerplanr, minimally nonouterplanar, nonminimally 


nonouterplanar, noneulerian, hamiltonian and graphs with crossing number one. 


Key Words: Pathos, path number, Smarandachely block graph, semitotal block graph, 
total block graph, pathos total semitotal block graph, pathos entire total block graph, pathos 


length, pathos point, inner point number. 


AMS(2010): 05075 
§1. Introduction 


The concept of pathos of a graph G was introduced by Harary [2], as a collection of minimum 
number of line disjoint open paths whose union is G. The path number of a graph G is the 
number of paths in a pathos. A new concept of a graph valued functions called the semitotal 
and total block graph of a graph was introduced by Kulli [5]. For a graph G(p,q) if B = 
U1, U2, U3,°°* ,Ur;7 > 2 is a block of G. Then we say that point u; and block B are incident 
with each other, as are ug and B and soon. If two distinct blocks B, and Bg are incident with 
a common cut point, then they are called adjacent blocks. The points and blocks of a graph 
are called its members. A Smarandachely block graph TY (G) for a subset V C V(G) is such 
a graph with vertices V U 6 in which two points are adjacent if and only if the corresponding 
members of G are adjacent in (V)q or incident in G’, where B is the set of blocks of G. The 
semitotal block graph of a graph G denoted T,(G) is defined as the graph whose point set is 
the union of set of points, set of blocks of G in which two points are adjacent if and only if 


1Received March 26, 2012. Accepted June 12, 2012. 


40 Muddebihal M. H. and Syed Babajan 


members of G are incident. The total block graph of a graph G denoted by Tg(G) is defined as 
the graph whose point set is the union of set of points, set of blocks of G in which two points 
are adjacent if and only if the corresponding members of G are adjacent or incident. Also, a 
new concept called pathos semitotal and total block graph of a tree has been introduced by 
Muddebihal [10]. The pathos semitotal graph of a tree T denoted by Pp, (T) is defined as the 
graph whose point set is the union of set of points, set of blocks and the set of path of pathos of 
T in which two points are adjacent if and only if the corresponding members of G' are incident 
and the lines lie on the corresponding path P; of pathos. The pathos total block graph of a 
tree T denoted by Pr,(T) is defined as the graph whose point set is the union of set of points, 
set of blocks and the set of path of pathos of T in which two points are adjacent if and only if 
the corresponding members of G are adjacent or incident and the lines lie on the corresponding 
path Pi of pathos. Stanton [11] and Harary [3] have calculated the path number for certain 
classes of graphs like trees and complete graphs. 

All undefined terminology will conform with that in Harary [1]. All graphs considered here 
are finite, undirected and without loops or multiple lines. The pathos total semitotal block 
graph of a tree T’ denoted by is defined as the graph whose point set is the union of set of points 
and set of blocks of T and the path of pathos of T in which two points are adjacent if and only 
if the corresponding members of T are incident and the lines lie on the corresponding path P; of 
pathos. The pathos entire total block graph of a tree denoted by is defined as the graph whose 
set of points is the union of set of points, set of blocks and the path of pathos of T in which 
two points are adjacent if and only if the corresponding members of T are adjacent or incident 
and the lines lie on the corresponding path P; of pathos. Since the system of pathos for T is 
not unique, the corresponding pathos total semitotal block graph and pathos entire total block 
graphs are also not unique. 

In Figure 1, a tree T and its semi total block graph T}(T) and their pathos total semitotal 
block graph are shown. In Figure 2, a tree T and its total block graph Tg(T) and their pathos 
entire total block graphs are shown. 

The line degree of a line wv in T, pathos length in T, pathos point in T’ was defined by 
Muddebihal [9]. If G is planar, the inner point number 7(G) of G is the minimum number of 
points not belonging to the boundary of the exterior region in any embedding of G in the plane. 
A graph G is said to be minimally nonouterplanar if i(G) = 1 as was given by Kulli [4]. 


We need the following results for our further results. 


Theorem A([10]) For any non-trivial tree T, the pathos semitotal block graph Pr,(T) of a tree 
T, whose points have degree d;, then the number of points are (2g +k+1) and the number of 


ie 
lines are (2 +2+ 5 D2 d? |, where k is the path number. 
i=1 


Theorem B((10]) For any non-trivial tree whose points have degree d;, the number of points 


12 
and lines in total block graph Tp(T) of a tree T are (2g +1) and (2 + 5 S- a) ; 


i=l 


Theorem C((10]) For any non-trivial tree T, the pathos total block graph Pr,(T) of a tree 


On Pathos Total Semitotal and Entire Total Block Graph of a Tree 41 


T, whose points have degree d;, then the number of points in Pr,(T) are (2g +k +1) and the 


P 
number of lines are (: +2+4+ S- a) , where k is the path number. 
i=1 











T T,(T) 


Figure 1 


Theorem D((7|) The total block graph Tp(G) of a graph G is planar if and only if G is 


outerplanar and every cut point of G lies on at most three blocks. 


Theorem E((6]) The total block graph Tp(G) of a connected graph G is minimally nonouter- 


42 Muddebihal M. H. and Syed Babajan 


planar if and only if, 

(1) G “éf a cycle, or 

(2) G is a path of length n > 2, together with a point which is adjacent to any two adjacent 
points of P. 


Theorem F'((8]) The total block graph Tp(G) of a graph G has crossing number one if and 
only af, 

(1) G ts outerplanar and every cut point in G lies on at most 4 blocks and G has a unique 
cut point which lies on 4 blocks, or 

(2)G is minimally nonouterplanar, every cut point of G lies on at most 3 blocks and exactly 


one block of G is theta-minimally nonouterplanar. 


Corollary A((1]) Every non-trivial tree T contains at least two end points. 


§2. Pathos Total Semitotal Block Graph of a Tree 


We start with a few preliminary results. 


Remark 2.1 The number of blocks in pathos total semitotal block graph P;,,(T') of a tree T 
is equal to the number of pathos in T. 


Remark 2.2 If the pathos length of the path P; of pathos in T is n, then the degree of the 
corresponding pathos point in P.(T) is 2n + 1. 


In the following theorem we obtain the number of points and lines in pathos total semitotal 
block graph P;,)(T) of a tree T. 


Theorem 2.1 For any non-trivial tree T, the pathos total semi total block graph Prs»(T) of a 
tree T, whose points have degree d;, then the number of points in Pisy(T) are (2g+k+1) and 


the number of lines are 


i=l 


doy os 
(% +24 3 y a) 
where k is the path number. 


Proof By Theorem A, the number of points in Pr,(T) are (2g+k+ 1), and by definition 
of Ps)(Z'), the number of points in P;s,(T') are (24g+k +1), where k is the path number. Also 


12 

by Theorem A, the number of lines in Pr,(T) are | 2q¢+2+ 5 S- d? |). The number of lines 
i=1 

in P:s)(T') is equal to the sum of lines in Py,(T) and the number of lines which lie on the lines 


(or blocks) of pathos, which are equal to q, since the number of lines are equal to the number 


of blocks in a tree T. Thus the number of lines in P;,,(T') is equal to 














ee os ee 
q+ Qq+2+5 > di )] =r 24 $50" 


i=1 i=l 


On Pathos Total Semitotal and Entire Total Block Graph of a Tree 43 


§3. Planar Pathos Total Semitotal Block Graphs 


A criterion for pathos total semitotal block graph P;,,(T) of a tree T to be planar is presented 


in our next theorem. 


Theorem 3.1 For any non-trivial tree T, the pathos total semi total block graph Prs»(T) of a 


tree T is planar. 


Proof Let T be a non-trivial tree, then in T,(T') each block is a triangle. We have the 
following cases. 


Case 1 Suppose G is a path, G = Pn : u,U2,U3,°+:,Un,n > 1. Further, V[T%(T)] = 
{ui, U2, U3,°°* ; Un, b1, b2, bs,-+- ,bn—i}, where 61, be, b3,--+ ,bn—1 are the corresponding block 
points. In pathos total semi total block graph P;..(T') of a tree T, the pathos point w is 
adjacent to, {u1, U2, U3,---,Un, b1, ba, bs,--- ,bn-1}. For the pathos total semitotal block graph 
Pisp(L) of a tree T, {urd  uow, ugbousw, ugb3uaw, +++ ,Un—1bn-1Unw} © V[Piso(L)], in which 
each set {Un—1bn—-1Unw} forms an induced subgraph as Ky. Hence one can easily verify that 
each induced subgraphs of corresponding set {u,—1b,-1Unw} is planar. Hence P;,»(T) is planar. 


Case 2 Suppose G is not a path. Then V [T7,(G)] = {u1, ue, us,--+ , Un, b1, be, b3,-++ , bn—1} and 
W1, W2, W3,°** , Wr be the pathos points.Since uy,—1Un is a line and Up—1Un = bn—1 € V [T)(G)]. 
Then in P:.)(G) the set {tn—1, bn—1, Un, w} Vn > 1, forms Ky as an induced subgraphs. Hence 











Pis5p(T) is planar. 





The next theorem gives a minimally nonouterplanar P,,.(T). 


Theorem 3.2 For any non-trivial tree T, the pathos total semitotal block graph Pis)(T) of a 


tree T is minimally nonouterplanar if and only if T = Ko. 


Proof Suppose T = K3, and P;.,(T') is minimally nonouterplanar, then T,(T) = K4 and 
one can easily verify that ¢(P:..(T')) > 1, a contradiction. 

Suppose T #4 K2. Now assume T = Ky 2 and Pys)(T) is minimally nonouterplanar. Then 
T)(T) = kz -k3. Since Ky,2 has exactly one pathos and let v be a pathos point which is 
adjacent to all the points of ks - ks in Pisy(T'). Then one can easily see that, i (Pis)(T)) > 1a 
contradiction. 

For converse, suppose T = Ko, then T,(T) = K3 and Prsy(T) = K4. Hence Pis4(T) is 


minimally nonouterplanar. 














From Theorem 3.2, we developed the inner point number of a tree as shown in the following 


corollary. 


Corollary 3.1 For any non-trivial tree T with q lines, i (Pisp(T)) = ¢. 


Proof The result is obvious for a tree with g = 1 and 2. Next we show that the result is 
true for g > 3. Now we consider the following cases. 


Case 1 Suppose T is a path, P : vy, v2,...,Un such that vyvo = e1,v2V3 = €2°++ 4 Un—1Un = 


44 Muddebihal M. H. and Syed Babajan 


€n—1 be the lines of P. Since each e;,1 < i < n—1, be a block of P, then in T,(P), each e; 
is a point such that V[T,(P)] = V(P)U E(P). In T,(P) each v1 e1v2, v3e203,° ++ , Un—1€n—1Un 
forms a block in which each block is k3. Since each line is a block in P,then the number of 
ks’s in Tb(P) is equal to the numbers of lines in P. In P;s4(P), it has exactly one pathos. 
Then V[Piso(P)] = V[Tp(P)] U {P} and P together with each block of T,(P) forms a block as 
Ps)(P). Now the points p, v1, €1, v2 forms k4 as a subgraph of a block P;,,(P). Similarly each 
{v2, €2, v3, D}, {v3, e3, V4, P},+++ » {Un—1, Cn—1, Un, p} forms ka as a subgraph of a block P,.,(P). 
One can easily find that each point e;,1 <7 < n-—1 lie in the interior region of ky, which 
implies that 7 (Prso(P)) = q. 


Case 2 Suppose T is not a path, then T' has at least one point of degree greater than two. Now 
assume T' has exactly one point v, degu > 3. Then T = K1,». If Prs)(T) has inner point number 
two which is equal to n = q. Similarly if n is odd then P,,,(T’) has n— 1 blocks with inner point 
number two and exactly one block which is isomorphic to k4. Hence ¢ [Pis5 (1.n)] = q. Further 
this argument can be extended to a tree with at least two or more points of degree greater two. 














In each case we have ¢[Pisp (T')] = ¢. 


In the next theorem, we characterize the noneulerian P;.4(T). 


Theorem 3.3 For any non-trivial tree T, the pathos total semitotal block graph Pis,(T) of a 


tree T is noneulerian. 


Proof We have the following cases. 


Case 1 Suppose A(T) < 2 and if p = 2 points, then P;,,(1) = K4, which is noneulerian. If T is 
a path with p > 2 points. Then in T,(T)) each block is a triangle such that they are in sequence 
with the vertices of Tb(T) as {v1, b1, v2, v1} an induced subgraph as a triangle in T;,(T). Further 
{v2, be, v3, va}, {u3, 03, U4, U3},°°+ 5 {Un—1,; bn, Un, Un—1}, in which each set form a triangle as an 
induced subgraph of T,(T'). Clearly one can easily verify that T,(T) is eulerian. Now this path 
has exactly one pathos point say k,, which is adjacent to v1, v2, U3,°++ , Un, 61, b2, b3,°°° ,bn—1 in 
Pis5)(L) in which all the points v1, v2, v3, ..., Un, b1, be, b3,-++ ,bn—-1 © Pisy(L) are of odd degree. 
Hence P;,4(T’) is noneulerian. 


Case 2 Suppose A(T) > 3. Assume T has a unique point of degree > 3 and also assume that 
T = Ky. Then in 7;(T) each block is a triangle, such that there are n number of blocks which 
are K3 with a common cut point k. Since the degree of a vertex k = 2n. One can easily verify 
that Tp (41,3) is eulerian. To form P;.,(T'), T = Kin, the points of degree 2 and the point k are 
joined by the corresponding pathos point which gives points of odd degree in P;,,(T'). Hence 














P,s)(T) is noneulerian. 


In the next theorem we characterize the hamiltonian P;.,(T). 


Theorem 3.4 For any non-trivial tree T, the pathos semitotal block graph Prs)(T) of a tree T 
is hamiltonian if and only if T is a path. 


Proof For the necessity, suppose T is a path and has exactly one path of pathos. 
Let V [Tp (T)] => {ui, U2,U3,°°° ,Un}{bi, ba, bs, sneer sOn-1}, where bi, ba, bs, seey bn—1 are 


On Pathos Total Semitotal and Entire Total Block Graph of a Tree 45 


block points of T. Since each block is a triangle and each block consists of points as By = 
{ui, bi, u2}, Bo = {ua, be, us},---,Bm = {Um,bm,Um+i}. In Prsy(T) the pathos point w is 
adjacent to {w1, U2, Us,°** » Un, 01, be, b3,-++ ,bn—1}. Hence V [Pish(T)] = {ur, ue, g,+++ , Un} U 
{b1, bo, bs, +++ ,bn—1} Uw form a spanning cycle as w, w1, b1, U2, b2, W2,°+* ,Un—1, 0n—1, Un, w of 
Pis)(L). Clearly P:;)(T) is hamiltonian. Thus the necessity is proved. 

For the sufficiency, suppose P;.,(T') is hamiltonian. Now we consider the following cases. 


Case 1 Assume T is a path. Then T has at least one point with degu > 3, V v € V(T), 
suppose TJ’ has exactly one point u such that degree u > 2 and assume G = T' = Ky,,,. Now we 
consider the following subcases of case 1. 


Subcase 1.1 For Ki,,,n > 2 and if n is even, then in T}(T) each block is kg. The number 
of path of pathos are = Since n is even we get ie blocks in P;s5(T'), each block contains two 
times of (A4) with some edges common. Since Pisy(T) has a cut points, one can easily verify 
that there does not exist any hamiltonian cycle, a contradiction. 





1 
Subcase 1.2 For Ky,,n > 2 and n is odd, then the number of path of pathos are “ , 


We asaploees ahh = 


is nonline disjoint subgraph of P;,,(T) and remaining blocks is (K4). Since P,,,(T') contain 








since n is odd we get blocks contains two times of (f(4) which 


a cut point, clearly P;,,(T) does not contain a hamiltonian cycle, a contradiction. Hence the 











sufficient condition. 





§4. Pathos Entire Total Block Graph of a Tree 


A tree T, its total block graph Tg (T), and their pathos entire total block graphs P.1)(T) are 
shown in Figure 2. We start with a few preliminary results. 


Remark 4.1 If the pathos length of path P; of pathos in T is n, then the degree of the 
corresponding pathos point in P.(T) is 2n + 1. 


Remark 4.2 For any nontrivial tree T’, the pathos entire total block graph P.1»(T) is a block. 


Theorem 4.1 For any non-trivial tree T, the pathos total block graph P.1»(T) of a tree T, whose 
points have degree d;, then the number of points in Pe(T) are (2g+k+1) and the number of 


P 
lines are (2 +2+4+ SB a) , where k is the path number. 


i=1 
Proof By Theorem C, the number of points in Pr,(T)are (2g+k+ 1), by definition of 
Pe»(T), the number of points in P.4,(T) are (2g+k-+1), where k is the path number in T. 


ie 
Also by Theorem B, the number of lines in Tg(T) are | 2g + 5 S- ie) . By Theorem C, The 
i=1 


Pp 
number of lines in Pr,(T) are | q+2+ d? |. By definition of pathos entire total block 
'B i Ma 


i=l 
graph P.1,(T) of a tree equal to the sum of lines in Pp, (T) and the number of lines which lie 
on block points b; of Tg(T) from the pathos points P;, which are equal to g. Thus the number 


46 Muddebihal M. H. and Syed Babajan 














Pp P 
of lines in Po (T) = (s+24 4] = (+24 oa), 


i=1 i=l 











T,(T) 


Figure 2 


§5. Planar Pathos Entire Total Block Graphs 


A criterion for pathos entire total block graph to be planar is presented in our next theorem. 


Theorem 5.1 For any non-trivial tree T, the pathos entire total block graph P.1»(T) of a tree 
T is planar if and only if A(T) < 3. 


Proof Suppose P.(T) is planar. Then by Theorem D, each cut point of T lie on at 
most 3 blocks. Since each block is a line in a tree, now we can consider the degree of cut 
points instead of number of blocks incident with the cut points. Now suppose if A(T) < 3, 
then by Theorem D, Tg(T) is planar. Let {b1, 62, b3,--- ,bp-1} be the blocks of T with p 
points such that b) = e1, bz = €2,--- ,bp_1 = €p_1 and P; be the number of pathos of T. Now 
V [Pew(T)| = V(G) VU b1, ba, 63,-++ ,bp-1 U{P;}. By Theorem D, and by the definition of pathos, 


On Pathos Total Semitotal and Entire Total Block Graph of a Tree 47 


the embedding of P.:»(T) in any plane gives a planar P.1,(T). 

Conversely, Suppose A(T) > 4 and assume that P.4,(T) is planar. Then there exists at 
least one point of degree 4, assume that there exists a vertex v such that degu = 4. Then 
in Tp(T), this point together with the block points form ks as an induced subgraph. Further 
the corresponding pathos point which is adjacent to the V(T’) in Tg(T) which gives P.i»(T) 
in which again ks as an induced subgraph, a contradiction to the planarity of Pe1)(T). This 











completes the proof. 





The following theorem results the minimally nonouterplanar P.+5(T). 


Theorem 5.2 For any non-trivial tree T, the pathos entire total block graph P.1»(T) of a tree 


T is minimally nonouterplanar if and only if T = ka. 


Proof Suppose T = kg and Per»(T) is minimally nonouterplanar. Then Tp(T) = kg and 
one can easily verify that, i(P.1(T')) > 1, a contradiction. Further we assume that T = Ki,2 
and P.4)(T) is minimally outerplanar, then Tg(T) is W, — x, where x is outer line of W,. Since 
F1,2 has exactly one pathos, this point together with W, — x gives W,+1. Also in P.1,(T’) and 
by definition of P.i»(T) there are two more lines joining the pathos points there by giving W,+3. 
Clearly, P.1,(T) is nonminimally nonouterplanar, a contradiction. 


For the converse, if T = ko, T p(T) = kg and P.4(T) = K4 which is a minimally nonouter- 














planar. This completes the proof of the theorem. 


Now we have a pathos entire total block graph of a path p > 2 point as shown in the below 
remark. 


Remark 5.1 For any non-trivial path with p > 2 points, i[P.1,(T)| = 2p—3. The next theorem 


gives a nonminimally nonouterplanar P.1(T). 


Theorem 5.3 For any non-trivial tree T, the pathos entire total block graph P.1»(T) of a tree 
T is nonminimally nonouterplanar except for T = ka. 


Proof Assume T is not a path. We consider the following cases. 


Case 1 Suppose T is a tree with A(T) > 3. Then there exists at least one point of degree 
at least 3. Assume v be a point of degree 3. Clearly, T = K,,3. Then by the Theorem F, 
i(Tp(T)] > 1. Since Tp(T) is a subgraph of P.1»(T'). Clearly, i (Peiw(T)) > 2. Hence Pery(T) is 
nonminimally nonouterplanar. 


Case 2 Suppose T is a path with p points and for p > 2 points. Then by Remark 5.1, 











t[Pew(T)| > 1. Hence Peyy(T) is nonminimally nonouterplanar. 





In the following theorem we characterize the noneulerian P.4y(T). 


Theorem 5.4 For any non-trivial tree T, the pathos entire total block graph P.1»(T) of a tree 


T is noneulerian. 


Proof We consider the following cases. 


48 Muddebihal M. H. and Syed Babajan 


Case 1 Suppose T' is a path P, with n points. Now for n = 2 and 8 points as follows. For 
p = 2 points, then P.4,() = K4, which is noneulerian. For p = 3 points, then P.,(T) is a 
wheel Wg together with two lines joining the non adjacent points in which one point is common 


for these two lines as shown in the Figure 3, which is noneulerian. 


b, b, 
eo 
P, 
L 
b, b, 
P, 
P.(T) 
Figure 3 
For p > 4 points, we have a path P : v1, v2, v3,...,Up. Now in path each line is a block. 
Then viva = e1 = bi, v2vg = €2 = be,...,Up-1Up = Ep-1 = bp-1, V €p-1 € E(G), and 





V bp-1 € V[Tp(P)]. In Tp (P), the degree of each point is even except b; and 6,1. Since 
the path P has exactly one pathos which is a point of P..»(P) and is adjacent to the points 
V1, V2, U3,---,Up, Of Tg (P) which are of even degree, gives as an odd degree points in Pery(P) 
including odd degree points b; and bp)_1. Clearly P.i,(P) is noneulerian. 


Case 2 Suppose T is not a path. We consider the following subcases. 


Subcase 2.1 Assume T has a unique point degree > 3 and T = Ky, with n is odd. Then in 
Tp (T) each block is a triangle such that there are n number of triangles with a common cut 
points k which has a degree 2n. Since the degree of each point in Tg (K1,,) is odd other than 
the cut point k which are of degrees either 2 or n +1. Then Pe4,(T) eulerian. To form P.1(T) 
where T = Kj, the points of degree 2 and 4 the point k are joined by the corresponding 
pathos point which gives (2n + 2) points of odd degree in Perp(Kin). Pet(T) has n points of 
odd degree. Hence P.1,(T) noneulerian. 

Assume that T = Ky,n, where n is even, Then in Tg (T) each block is a triangle, which 
are 2n in number with a common cut point k. Since the degree of each point other than k is 
either 2 or (n +1) and the degree of the point & is 2n. One can easily verify that Tp (Kin) 
is noneulerian. To form Per»(T) where T = Ky,n, the points of degree 2 and 5 the point & are 
joined by the corresponding pathos point which gives (n + 2) points of odd degree in Peyy(T). 


On Pathos Total Semitotal and Entire Total Block Graph of a Tree 49 


Hence P.+(T) noneulerian. 


Subcase 2.2 Assume T has at east two points of degree > 3. Then V[Tp(T)] = V(G) U 
bi, b2, b3,...,bp, V bp € E(G). In Tg (T), each endpoint has degree 2 and these points are 
adjacent to the corresponding pathos points in P.4,(T) gives degree 3, From case 1, Tree T 
has at least 4 points and by Corollary [A], Pei(T) has at least two points of degree 3. Hence 











P.1»(T) is noneulerian. 





In the next theorem we characterize the hamiltonian P.4,(T). 


Theorem 5.5 For any non-trivial tree T, the pathos entire total block graph P.1»(T) of a tree 


T is hamiltonian. 


Proof we consider the following cases. 


Case 1 Suppose T is a path with {uj, ue, us,...,Un} € V(T) and 64, be, b3, ...,bm be the 
number of blocks of T such that m = n—1. Then it has exactly one path of pathos. Now 
point set of Tp (T), V [Ta(T)] = {ur,u2,--: , un} U {b1, bo,...,bm}. Since given graph is a 
path then in Tg (T), 61 = e1,b2 = €2,...,bm = Cm, such that by, be, bs,...,0m C V [Te (T)]. 
Then by the definition of total block graph, {u1, u2,...,Um—1, Um} U {b1, b2,.--,bm—1, bm} U 
{byu1, bou2,...-bmUn—1, mtn} form line set of Tg (T) (see Figure 4). 











b, b, b, b,, 
P e e ° SSeS eee) 
u, Uy Us Uy Uy U,, 
b, b, b, b,, 
na: “~~ N\LZN LS 
U, Uy Us Uy Uy U, 
Figure 4 


Now this path has exactly one pathos say w. In forming pathos entire total block graph of a 
path, the pathos w becomes a point, then V [P.15(T)] = {u1, ua,-++ ,Un}U{b1, ba,...,bm}U{w} 
and w is adjacent to all the points {u1,u2,--- , U,} shown in the Figure 5. 

In P.»(T), the hamiltonian cycle w, ur, 01, Ua, be, U2, Us, b3,°++ ,Un—1, 0m; Un, w exist. Clearly 
the pathos entire total block graph of a path is hamiltonian graph. 


Case 2 Suppose T is not a path. Then T has at least one point with degree at least 3. Assume 
that T has exactly one point u such that degree > 2. Now we consider the following subcases 
of Case 2. 


Subcase 2.1 Assume T = Kj,,,n > 2 and is odd. Then the number of paths of pathos are 
1 
is Let V [Tp(T)] = {ui, u2,..-,Un, 01, b2,-.., bmi}. By the definition of pathos total 


block graph. By the definition P.w(T) V [Pew(T)] = {u1, ua,.--, Un, b1, b2,.-.,bn—-1} U {pi, pa, 
- ;Pn+1/2}- Then there exists a cycle containing the points of By the definition of P.4,(T) as 





50 Muddebihal M. H. and Syed Babajan 


pi, U1, b1, be, U3, pa, U2, b3, U4,+*+ , pi and is a hamiltonian cycle. Hence P.:»(T) is a hamiltonian. 

















Figure 5 


Subcase 2.2 Assume T = Kj,,,n > 2 and is even. Then the number of path of pathos 
are - then V [Tp(T)] = {u1, u2,-++ Un, b1, b2,-++ ,bn-1}. By the definition of pathos en- 
tire total block graph P..(T) of a tree T. V [Pes(T)] = {ur, ua,--+ , Un, b1, b2,--+ ,bn—1} U 
{P1;P2;*** ;Pn/2}. Then there exist a cycle containing the points of Pero(T) as pi, us, b1, be, 
U3, P2, U4, bs, b4,--+ , pi and is a hamiltonian cycle. Hence P.4,(T) is a hamiltonian. 

Suppose 7’ is neither a path nor a star, then T contains at least two points of degree 
> 2. Let u1,uU2,uUg,°---,Un be the points of degree > 2 and vj, v2,v3,:::,Um be the end 
points of T. Since end block is a line in T, and denoted as bj, b2,--- ,b, ,then V [Tp(T)] = 
{ui, U2,---,Un} U {01, v2,...Um} U {b1, be,..., be },and tree T has p; pathos points, i > 1 and 
each pathos point is adjacent to the point of T where the corresponding pathos lie on the points 
of T. Let {pi,pe2,--- ,pi}be the pathos points of T. Then there exists a cycle C containing all 
the points of P.w(T), as pr, v1, b1, v2, po, U1, b3, U2, D3, U3, b4,; Um—1; On—1, bn, Um;---, Pi- Hence 











P.1»(T) is a hamiltonian cycle. Clearly, P..»(T') is a hamiltonian graph. 





In the next theorem we characterize P.4,(T) in terms of crossing number one. 


Theorem 5.6 For any non-trivial tree T, the pathos entire total block graph P.1»(T) of a tree 
T has crossing number one if and only if A(T) < 4, and there exist a unique point in T of 


degree 4. 
Proof Suppose P.1,(T') has crossing number one. Then it is nonplanar. Then by Theorem 


5.1, we have A(T’) < 4. We now consider the following cases. 


Case 1 Assume A(T’) = 5. Then by Theorem [F], Tg (T) is nonplanar with crossing number 
more than one. Since Tg (T) is a subgraph of Pr, (T). Clearly cr (Pr, (T)) > 1, a contradiction. 


Case 2 Assume A(T) = 4. Suppose T has two points of degree 4. Then by Theorem F, Tz (T) 
has crossing number at least two. But Tg (T’) is a subgraph of P.»(T). Hence cr (Pew(T)) > 1, 


On Pathos Total Semitotal and Entire Total Block Graph of a Tree 51 


a contradiction. 


Conversely, suppose T’ satisfies the given condition and assume T' has a unique point v of 


degree 4. The lines which are blocks in T such that they are the points in Tg (T). In Tg (T), 
these block points and a point v together forms an induced subgraph as ks. In forming P..»(T), 


the pathos points are adjacent to at least two points of this induced subgraph. Hence in all 


these cases the cr (P.1,(T')) = 1. This completes the proof. 














References 


[1] Harary F., Graph Theory, Addison-Wesley Reading. Mass. (1969). 
[2] Harary F., Covering and packing in graphs-I, Annals of Newyork Academy of Sciences, 


[3 








(1970), pp 198-205. 

Harary F. and Schweak A.J., Evolution of the path number of graph, Covering and pack- 
ing in graph-II, Graph Theory and Computing, Ed.R.C. Read, Academic Press, Newyork 
(1972), pp 39-45. 

Kulli V.R., On minimally nonouterplanar graphs, Proceeding of the Indian National Science 
Academy, Vol-41, Part-A, No.3, (1975), pp 275-280. 

Kulli V.R., The semi total-block graph and Total-block graph of a graph, Indian J. Pure 
€& App. Maths, Vol-7, No.6, (1976), pp 625-630. 

Kulli V.R. and Patil H.P., Minimally nonouterplanar graphs and some graph valued func- 
tions, Journal of Karnataka University Science, (1976), pp 123-129. 

Kulli V.R. and Akka D.R., Transversability and planarity of total block graphs, Jour. 
Math. Phy. Sci., Vol-11, (1977), pp 365-375. 

Kulli V.Rand Muddebihal M.H., Total block graphs and semitotal block graphs with cross- 
ing numbers, Far East J. Appl. Math., 4(1), (2000), pp 99-106. 

Muddebihal M.H., Gudagudi B.R. and Chandrasekhar R., On pathos line graph of a tree, 
National Academy Science Letters, Vol-24, No.5 to 12, (2001), pp 116-123. 

Muddebihal M.H. and Syed Babajan, On pathos semitotal and total block graph of a tree 
(to appear). 





Stanton R.G., Cowan D.D. and James L.O., Some results on the path numbers, Preoceed- 
ings of Lousiana Conference on Combinatorics, Graph Theory and Computing, (1970), pp 
112-135. 


Math.Combin. Book Ser. Vol.2(2012), 52-58 


On Folding of Groups 


Mohamed Esmail Basher 
(Department of Mathematics, Faculty of Science in Suez, Suez Canal University, Egypt) 
E-mail: m_e_-basher@yahoo.com 


Abstract: The aim of our study is to give a definition of the folding of groups and study the 
folding of some types of groups such as cyclic groups and dihedral groups, also we discussed 


the folding of direct product of groups. Finally the folding of semigroups are investigated. 
Key Words: Folding, multi-semigroup, multi-group, group, commutative semigroup. 


AMS(2010): 54005, 20K01 
§1. Introduction 


In the last two decades there has been tremendous progress in the theory of folding. The notion 
of isometric folding is introduced by 5S. A. Robertson who studied the stratification determined 
by the folds or singularities [10]. The conditional foldings of manifolds are defined by M. El- 
Ghoul in [8]. Some applications on the folding of a manifold into it self was introduced by P. 
Di. Francesco in [9]. Also a folding in the algebras branch introduced by M.El-Ghoul in [7]. 
Then the theory of isometric foldings has been pushed and also different types of foldings are 
introduced by E. El-Kholy and others [1,2,5,6]. 


Definition 1.1([4]) A non empty set G on which is defined s > 1 associative binary operations 
*x is called a multi-semigroup, if for all a,b € G,ax*b © G, particularly, if s = 1, such a 


multi-semigroup is called a semigroup. 
Example 1 Z, = {0,1,2,...,p — 1} is a semigroup under multiplication p, p € Zt. 


Definition 1.2([4]) A subset H is a subsemigroup of G if H is closed under the operation of 
G ; that it ifaxbe H for alla,be H. 


Definition 1.3 A multi-group (G,O) is a non empty set G together with a binary operation 
set O onG such that for * € O, the following conditions hold: 

(1) Va,be G thenaxbeEG. 

(2) There exists an element e € G such thataxe =exa=a, for allaeG. 


1 1 


(3) Fora €G there is an element a~! in G such thataxa~'=a7!*xa=e. 


Particularly, if |O| = 1, such a multi-group is called a group and denoted by G 
lReceived January 17, 2012. Accepted June 14, 2012. 


2Current Address: Qassim University,College of Science, Dept. of Math., P. O. Box 6644, Buriedah 51452, 
Al Qassim, Saudi Arabia 


On Folding of Groups 53 


A group G is called Abelian if ax b = bx a for all a,b € G. The order of a group is its 
cardinality, i.e., the number of its elements. We denote the order of a group G by |G}. 


Definition 1.4([3]) The group G is called a cyclic group of order n, if there exists an element 
g € G, such that G = (g) = {g |g” = 1}. In this case g is called a generator of G. 


Definition 1.5([3]) The dihedral group Don, of order 2n, is defined in the following equivalent 
ways: Don = {a,b ae oP S41 ab = a}. 








Definition 1.6([3]) A subset H is a subgroup of G ,H < G, if H is closed under the operation 
of G ; that it ifa*xbe A for alla,be H. 


Definition 1.7([3]) The trivial subgroup of any group is the subgroup {e}, consisting of just 


the identity element. 


Definition 1.8([3]) A subgroup of a group G that does not include the entire group itself is 
known as a proper subgroup, denoted by H <G. 


Theorem 1.1 Every subgroup of a cyclic group is cyclic. 


§2. Group Folding 


In this section we give the notions of group folding and discuss the folding of some kinds of 
groups 


Definition 2.1 Let G,,Gz are two groups, The group folding g.f of Gi into G2 is the map 
f : (Gi, *) (Go, 0) st. 
VaeG, fla)=b, fla )=o! 


where b € Gg and f(G1) is subgroup of Go. 
Definition 2.2 The set of singularities \> f is the set of elements a; € G such that f(a;) = a;. 


Definition 2.3 A group folding is called good group folding g.g.f if H is non trivial subgroup 
of G. 


Proposition 1.1 The limit of group folding of any group is {e}. 


Proof Let G be any group and since any group has two trivial subgroups (G, *), ({e} , *) ,where 
({e},*) is the minimum subgroup of G. Then if we define a sequence of group folding 
fi: (G,*) — (G,*), such that f(a;) =); , f(a;+) =b;*. We found that lim f;(G) = {e}. 














Theorem 2.1 Let G be cyclic group G = {g:g? =1}, where p is prime. Then there is no 
g-g-.f map can be defined on G. 


Proof Given G is cyclic group of order p, since p is prime. Then there is no proper subgroup 











can be found in G. Hence we can not able to defined any g.g.f map on group G. 





54 Mohamed Esmail Basher 


1 {XQ 


Theorem 2.2 Let G be cyclic group G = {g: g? =1}, where p = qf" q5?---¢0" and q, G2,°+* 4 dn 

are distinct prime number. Then the limit of g.g.f map of G is the proper subgroup , H = 
Pp 

{9% : (g#)* =1}. 


a1 {a2 


Proof Since G be cyclic group and |G] = p = q["4q5?--- 2", %,425°°*5%n are distinct 
prime number. Then there exist proper subgroup H < G such that |H| = k. So we can defined 
g.g.f map fi :G— G, such that f\(G) = H, after this there exist two cases. 


Case 1. _ If k is prime number then we can not found a proper subgroup of H and so 
lim fi(G@) =H and k= ql Si<n, f(G) =H = {o% : (gh) * = 1h. 

Case 2. Ifk is not prime. Then k = qj'"q5? ---q%",m <n, hence there exist a proper subgroup 
Aer, A| =k. Thus we can defined a g.g.f map f2 : H —> H, such that fo(H) = H. Again 
if |#| is prime. Then lim f;(G) =H, k=q@,1<i<m, fi(G) =H = {9% : (g%)% = i} or, 
if |H | =k is not Srinie. Then we can repeat the Case II again. Finally the limit of g.g.f of G 
is the subgroup H = {9% : (g%)% = 1} : 

















Corollary 2.1 If p= q®% then the limit of g.g.f map of G is a subgroup H = {9° : (9%) = i} : 


Example 2 Let G = {g:9'!2 =1} bea cyclic group, |G| = 12 = 27.3, so we can defined a 
g.g.f map as the following f; : G — G, such that: 


fi) =1, Ag’) = 97, Ag’) = 9”, 
filo) =94, A) =95, Ag®) =9", 
fig’) =97, fg’) =o", 

fig?) =9*, Ao?) =9°, 

filg) = 9°, Ai(g’’) = 9° 





and f1(G) = H = {1,9?,9*, 9°, 98, g'°}, since the order of H is not prime then we can defined 
ag.g.f map as the following f2 : H —> H such that 


fo(1) = 1, fa(g°) =1 


and fo(H) = H = {1,9*, 98} is proper subgroup of H. Since the order of H is prime, then 
lim fi(G) = H = {9'\(9*)? = 1}. 

Proposition 2.2 For any dihedral group Do, = {a,b |a = b" = 1, bab= 1}, we can defined a 
g-g-.f map. 


a1 {a2 


Theorem 2.3 Let Do, be a dihedral group ,where n = qy* qo? ++: ae™ and q1,92,°°* Um are 
distinct prime number. Then the limit of g.g.f of Dan is one of these H; = {1, ab'} = 
1 Dect Sade Hi {vs (bu) = bi ae year 





On Folding of Groups 55 


Proof Let Don = {a,b |a = b” = 1, bab = 1} be a dihedral group of order 2n. Then the 
group D2, has n proper subgroups H; = {1,ab'} ,i = 1,2, ...,n of order 2, and so we can defined 
ag.g.f map f : Den, —> Don, such that f(Don) = Hi. 

Also since the dihedral group has proper cyclic subgroup H = {b|b” = 1}. Then we can 
defined a g.g.f map f : Don —> Don, such that f(De,) = {b|b” = 1}, and since the subgroup 
H = {b|b” = 1} be cyclic group of order n = gf g5?--- qo. Thus by applying the Theorem 
2.2 we get that lim fi(Dan) =H = {ov (bv) a = i} i= 1,2,-++,m. 

















§3. Group Folding of the Direct Product of Groups 


In this section we discuss the group folding of direct product of groups. Let fi : (Gi,*) > 
(Gi,*), fo : (Go,*) (Go, *) are two g.g.f maps. Then we define the direct product of the 
fi, fa as the following: 


fi x fo : (Gy x G2,*) =? (Gi x G2,*) 
Va €Gi,b€ Go, (fi x fe) (a,) = (fila), fo(0)) 


Theorem 3.1 The direct product of two g.g.f maps are g.g.f map also, but the converse is 
not always true. 


Proof Since fy : (Gi,*) — (Gi,*), fo : (Go,*) — (Go,*) are two g.g.f maps then there 
exist two proper subgroups Hy, H2 of G1, G2 respectively, such that f1(Gi) = M1, fo(G2) = Ho. 
As the direct product of the any two proper subgroups are proper subgroups. Hence Hy; x Hp < 
G x Gp. Now we will proof that the map, f* = fi x fo: Gi x Gz — G, Xx G2 is g.g.f map. 
Let a,b € G1, G2 and c,d € Hj, H2 respectively, then we have: 


f* (a,b) = (fi x fa) (a,b) = (fila), f(b) = (Gd) € A x Aa, 
ft fabs") = (fi x fa) (a 1b ig) = (c ad *) E Ay x Ao. 





Hence the map f* is g.g.f map. To proof the converse is not true, let G; = {91 o2= 1} 
G2 = {go | B= 1} be cyclic groups and since the order of them are prime then from Theorem 
2.1, we can not able to define a g.g.f map of them. But the direct product of G1, G2 is 


Gi x G2 = {(1, Ly, (1, 92), (1, 93), (1, 1), (91,92), (91,95) ¢ 


and since the |(G; x G2)| = 6. Hence G; x Gz has a proper subgroup H = {(1,1), (1, g2)} and 
so we can define the g.g.f map f* : G1 x Gz — G, x G2 as the following: 


FG, 1) = G, 1), 

f*(1, g2) = 1,92), F*(g1,1) = (1, 1), 
f*(g1, 92) = (1, 92), 

f*(91,.92) = (A, 92): 














This completes the proof. 


56 Mohamed Esmail Basher 


§4. Folding of Semigroups 


In this section we will be discuss the folding of semigroups into itself. Let (G,*«) be a commu- 
tative semigroup with identity 1, i.e. a monoid. 


Definition 4.1([4]) A nonzero element a of a semigroup G is a left zero divisor if there exists 
a nonzero b such thata*xb=0. Similarly, a is a right zero divisor if there exists a nonzero 


element cE G such that cx a= 0. 


The element a is said to be a zero divisor if it is both a left and right zero divisor. we will 
denote to the set of all zero-divisors by Z(G), and the set of all elements which have the inverse 
by I(G). 


Definition 4.2 The zero divisor folding of the semigroup G, z.d.f, is the map fz : (G,*) > 
(G,x*), st. 


0 ifx=0 
filz)=4 a ifxexa=0, 27,a40 
x ifxxa#0, r1,a40 


where a € Z(G). 


Note that f,(G) may be semigroup or not. We will investigate the zero divisor folding for 
Zy semigroups. 


Definition 4.3 Let Zp be a semigroup under multiplication modulo p. The z.d.f map of Zp 
is the map fz, : (G,.) > (G,.), st. 


0 ifx=0 
© ifxq #0, xq #0 


where q € Z(Zy ), is the greatest divisor of p. 
Proposition 4.1 If the order of Z, is prime. Then f,(G) =G, i.e. fz is identity map. 


Proof Since the order of semigroup Z, is prime. Then the semigroup Z, has not got any 
zero divisor, and so the z.d.f which can defined on Z, the identity map f,(x) = 2, for all 
LE Zp. 














Theorem 4.1 Let Zpbe semigroup of order p, then z.d.f of Zp into itself is a subsemigroup 
under multiplication modulo p. Has one zero divisor if 4| p or has not any zero divisor if 4{ p. 


Proof Let Z, be semigroup under multiplication modulo p. Then Z, consists of two subsets 
Z(Zp), I(Zp). 


On Folding of Groups 57 


Case 1. If p is even, then the z.d.f map defined as follows: 
0 ifs =0; 
f.(~)=4 § ifee Z(Z,), xis even; 
ifx€ Z(Z,), xis odd or z € I(Zy), 


8 


where 5 is the greatest divisor of p. Hence f,(Zp) = I(Zp)U4 0, S U1,°°° stn}, where £1,°°- ,2n 
are odd zero divisors and x;.2; # 0, for all i,j = 1,---,n. Notice that f,(Z, ) = I(Zp) U 
{0, = X1,°*+,4np is subsemigroup under multiplication modulo p. If 4 | p then a5 = 0, hence 
the subsemigroup f,(Z,) has one zero divisor = Otherwise, if 4 { p then a . #0. And so 
H =I1(Z,)U {0, a1, vee ,an is subsemigroup under multiplication modulo p without any 
zero divisor. 


Case 2. If p is odd, then the z.d.f map defined as follows: 
0 ifx=0; 
f(t)=4 q¢ ifee Z(Z,), zis odd; 
x ifxé Z(Zp), x is even or x € I(Z,), 
where q is the greatest divisor of p. Hence f,(Z,) = I(Zp)U{0,q,21,--: ,2n}, where x1,--- ,@ 


are even zero divisors and x;.x; # 0 for all i,j = 1,---,n. Notice that f,(Z,) = I(Zp) U 
{0,¢,21,°+: ,2n} is subsemigroup under multiplication modulo p, and since p is odd. Then 














f.(Z— p) has not any zero divisor. 


Corollary 4.1 If Z, be semigroup under multiplication modulo p and p = (q)"" ,meéN. Then 
f:(Zp) = I(Zp) U {0, geo is subsemigroup under multiplication modulo p. 


Example 3. (1) Let Zio = {0,1,2,3,--- ,9} be semigroup under multiplication modulo 10. 
Since p = 10 is even then the z.d.f. map defined as follows: 


0 ifx=0; 
f-z)={ 5 ifxe {2,4,8,6}; 
x ifae {1,3,7,9,5}. 
Thus f.(Zio) = {0,1,3,7,9,5}. Obviously, f,(Zio) is a subsemigroup under multiplication 
modulo 10. Since 410, then f,(Zi9) has not any zero divisor. 


(2) Let Zi2 = {0,1, 2,3, cdots, 11} be a semigroup under multiplication modulo 12. Since 
p = 12 is even then the z.d.f map defined as follows: 


0 ifx=0; 
fz(z)=¢ 6 if x € {2,4,6,8, 10}; 
a iffe {1,3,5, 7,9}. 


Hence f.(Z12) = {0,1,3,7,9,5,6}. Obviously, f.(Zi2) is a subsemigroup under multiplication 
modulo 12 and 6 is a zero divisor. 


58 


Mohamed Esmail Basher 


References 


1 








E.EL-Kholy and M. EL-Ghoul, Simplicial foldings, Journal of the Faculty of Education, 
18(1993), 443-455. 

H.R.Farran, E.EL-Kholy and $.A.Robertson, Folding a surface to a polygon, Geometriae 
Dedicata, 63(1996), 255-266. 

John A.Beachy, William D.Blair, Abstract Algebra (3th edition), Waveland Pr. Inc, 2006. 
J.M.Howie, An Introduction to Semigroup Theory, Academic Press, 1976. 

M.Basher, On the Folding of Finite Topological Space, International Mathematical Forum, 
Vol. 7, No.15(2012), 745 - 752. 

M.EI-Ghoul, M.Basher, The invariant of immersions under isotwist folding, KYUNGPOOK 
Math. J., 46(2006), 139-144. 

M.El-Ghoul, $.I.Nada and R.M.Abo Elanin, On the folding of rings, International Journal 
of Algebra, 3(2009), 475-482. 

M.El-Ghoul , Folding of Manifolds, Ph.D. Thesis, Tanta Univ., Egypt, 1985. 
P.DL-Francessco, Folding and coloring problem in mathematics and physics, Bulletin of 
the American Mathematics Socitey, 37(2000), 251-307. 

5.A.Robertson, Isometric folding of Riemannian manifolds, Proceedings of the Royal Society 
of Edinburgh, 79:3-4(1977), 275-284. 





Math.Combin. Book Ser. Vol.2(2012), 59-70 


On Set-Semigraceful Graphs 


Ullas Thomas 


Department of Basic Sciences, Amal Jyothi College of Engineering 


Koovappally P.O. - 686 518, Kottayam, Kerala, India 


Sunil C. Mathew 
Department of Mathematics, St.Thomas College Palai, Arunapuram P.O. - 686 574, Kottayam, Kerala, India 


E-mail: ullasmanickathu@rediffmail.com, sunilcmathew@gmail.com 


Abstract: This paper studies certain properties of set-semigraceful graphs and obtain 
certain bounds for the order and size of such graphs. More set-semigraceful graphs from 


given ones are also obtained through various graph theoretic methods. 
Key Words: Set-indexer, set-graceful, set-semigraceful. 


AMS(2010): 05C78 
§1. Introduction 


In 1986, B. D. Acharya introduced the concept of set-indexer of a graph G which is an as- 
signment of distinct subsets of a finite set X to the vertices of G subject to certain conditions. 
Based on this, the notions of set-graceful and set-semigraceful graphs were derived. Later many 
authors have studied about set-graceful graphs and obtained many significant results. 

This paper sheds more light on set-semigraceful graphs. Apart from many classes of set- 
semigraceful graphs, several properties of them are also investigated. Certain bounds for the 
order and size of set-semigraceful graphs are derived. More set-semigraceful graphs from given 
ones are also obtained through various techniques of graph theory. 


§2. Preliminaries 


In this section we include certain definitions and known results needed for the subsequent 
development of the study. Throughout this paper, J, m and n stand for natural numbers 
without restrictions unless and otherwise mentioned. For a nonempty set X, the set of all 
subsets of X is denoted by 2*. We always denote a graph under consideration by G and its 
vertex and edge sets by V and EF respectively and G’ being a subgraph of a graph G is denoted 
by G’ C G. When G’ is a proper subgraph of G we denote it by G’ C G. By the term graph 
we mean a simple graph and the basic notations and definitions of graph theory are assumed 
to be familiar to the readers. 


1Received December 1, 2011. Accepted June 15, 2012. 


60 Ullas Thomas and Sunil C. Mathew 


Definition 2.1({1]) Let G = (V, E) be a given graph and X be a nonempty set. Then a mapping 
f:V 2%, orf: E> 2%, orf: VUE — 2% is called a set-assignment or set-valuation of 


the vertices or edges or both. 


Definition 2.2([1]) Let G be a given graph and X be a nonempty set. Then a set-valuation 
f: VUE — 2% is a set-indexer of G if 


1. f(uv) = f(u) @ f(v),Vuv © E, where ‘®’ denotes the binary operation of taking the 


symmetric difference of the sets in 2* 
2. the restriction maps f\|v and f\z are both injective. 


In this case, X is called an indexing set of G. Clearly a graph can have many indexing sets and 
the minimum of the cardinalities of the indexing sets is said to be the set-indexing number of 


G, denoted by 7(G). The set-indexing number of trivial graph K, is defined to be zero. 
Theorem 2.3([1]) Every graph has a set-indezer. 
Theorem 2.4([1]) Jf X is an indexing set of G=(V,E). Then 


(i) |E| <2'*!—1 and 
(it) [log.(|E| + 1)] < y(G) < |V| —1, where | ] is the ceiling function. 


Theorem 2.5({1]) If G’ is subgraph of G, then 7(G’) < 7(G). 
Theorem 2.6([3]) The set-indexing number of the Heawood Graph is 5. 
Theorem 2.7([2]) The set-indexing number of the Peterson graph is 5. 


Theorem 2.8([13]) Jf G is a graph of order n, then y(G) > y(Kijn-1). 





Theorem 2.9((13]) (Kim) =n +1 if and only if 2" <m < 2"+1—-1, 
Theorem 2.10([15]) y(Pm) =n +1, where 2" <m< 2"+1-1, 


Definition 2.11([17]) The double star graph ST(m,n) is the graph formed by two stars Kim 
and Ky, by joining their centers by an edge. 


Theorem 2.12((16]) For a double star graph ST(m,n) with |V| = 2!, 1 > 2, 


l if m is even, 


y(ST(m,n)) = eat 
[+1 ifm is odd. 


Theorem 2.13((16]) y(ST(m,n)) =14+1 if2'+1<|V| < 24 -1;1>2. 
Theorem 2.14([1]) y(Cs) = 4. 


Theorem 2.15([1]) y(Ce) = 4. 


On Set-Semigraceful Graphs 61 


Definition 2.16({11]) The join Ky V Py-1 of Ky and P,_ is called a fan graph and is denoted 
by Fy. 


Theorem 2.17([15]) y(Fn) =m+1, where m = [logon] and n> 4. 
Definition 2.18([6]) The double fan graph is obtained by joining P, and Ko. 


n-1 fl<n<5 
n-2 f6<n<7 


Theorem 2.19([1]) y(Kn) = 


6 if 8<n<9 
Theorem 2.20((1]) y(n) =47 if 10<n< 12 
8 if B<n<15 
Definition 2.21({10]) For a graph G, the splitting graph S'(G) is obtained from G by adding 


for each vertex v of G, a new vertex say v' so that v' is adjacent to every vertex that is adjacent 


to v. 


Definition 2.22([4]) An n-sun is a graph that consists of a cycle C,;, and an edge terminating 


in a vertex of degree one attached to each vertex of Cy. 


Definition 2.23((8]) The wheel graph with n spokes, W,,, is the graph that consists of an n-cycle 


and one additional vertex, say u, that 1s adjacent to all the vertices of the cycle. 


Definition 2.24([11]) The helm graph H,, is the graph obtained from a wheel W, = Cy, V Ky 
by attaching a pendant edge at each verter of Cy. 


Definition 2.25({10]) The twing is a graph obtained from a path by attaching exactly two 


pendant edges to each internal vertex of the path. 


Definition 2.26((3]) The triangular book is the graph KyV Nm, where Ny is the null graph of 


order m. 


Definition 2.27((6]) The Gear graph is obtained from the wheel by adding a vertex between 
every pair of adjacent vertices of the cycle. 


Definition 2.28({10]) Embedding is a mapping ¢ of the vertices of G into the set of vertices of 
a graph H such that the subgraph induced by the set {¢(u) : u€ V(G)} is isomorphic to G; for 


all practical purposes, we shall assume then that G is indeed a subgraph of H. 


Definition 2.29([1]) A graph G is said to be set-graceful if 7(G) = logo(|E| +1) and the 
corresponding optimal set-indexer is called a set-graceful labeling of G. 


Theorem 2.30([9]) Every cycle Con_1, n > 2 is set-graceful. 
Theorem 2.31([10]) K3,5 is not set-graceful. 


Theorem 2.32([15]) y(Han_1) =n+4+2 for n> 2. 


62 Ullas Thomas and Sunil C. Mathew 


Theorem 2.33([1]) The star Ky2n_1 is set-graceful. 


§3. Certain Properties of Set-Semigraceful Graphs 


In this section we derive certain properties of set-semigraceful graphs and obtain certain bounds 
for the order and size of such graphs. 


Definition 3.1([1]) A graph G is said to be set-semigraceful if y(G) = [log2(|E| + 1)]. 


Remark 3.2 (1) The Heawood graph is set-semigraceful by Theorem 2.6. 

(2) The stars are set-semigraceful by Theorem 2.9. 

(3) The Paths P,; n 4 2™, m > 2 are set-semigraceful by Theorem 2.10. 

(4) Ky, is set-semigraceful if n € {1,--- ,7,9,12} by Theorems 2.19 and 2.20. 

(5) The Double Stars ST(m,n); m+n 4 2!, m is odd are set-semigraceful by Theorems 
2.12 and 2.13. 

(6) The helm graph H2n_ is set-semigraceful by Theorem 2.32. 

(7) All set graceful graphs are set-semigraceful. 

(8) The path P; is set-semigraceful but it is not set-graceful. 

(9) A graph G of size 2” — 1 is set-semigraceful if and only if it is set-graceful. 

(10) Not all graphs of size 2” — 1 is set-semigraceful. For example K3,5 is not set- 
semigraceful by Theorem 2.31. 


The following theorem is an immediate consequence of the above definition. 


Theorem 3.3 Let G be a (p,q)-graph with y(G) =m. Then G is set-semigraceful if and only 
if 27-1 <q@<2™-1. 


Corollary 3.4 Let G’ be a (p,q') spanning subgraph of a set-semigraceful (p,q)-graph G with 
qd >2-!, Then G' is set-semigraceful. 














Proof The proof follows from Theorems 2.4 and 3.3. 


Remark 3.5 (1) The Peterson graph is not set-semigraceful by Theorem 2.7. 

(2) The paths Pym; m > 2 are not set-semigraceful by Theorem 2.10. 

(3) The double stars ST (m,n); m+n = 2!, m is odd are not set-semigraceful by Theorem 
2.12. 

(4) K,, is not set-semigraceful if n € {8,10, 11,13, 14,15} by Theorem 2.20. 


Corollary 3.6 Let T be a set-semigraceful tree of order p, then 21-141 < p< 21, 


While Theorem 3.3 gives bounds for the size of a set-semigraceful graph in terms of the 
set-indexing number, the following one gives the same in terms of its order. 


Theorem 3.7 Let G be a set-semigraceful (p,q)-graph. Then 





gllogap|—1 Sas 9 | loge (PL +1)] 24. 


On Set-Semigraceful Graphs 63 


Proof By Theorems 2.4, 2.5 and 2.8, we have 


logan] <1 Kaye) $(G) = [logela +191 < tom Z2 2 +a). 


Now by Theorem 3.3 we have 








gllogep|—1 <q< 9 | loge (PL +1)] a 











Remark 3.8 The converse of Theorem 3.7 is not always true. By Theorem 2.14 we have, 
[loga(|E(Cs)| + 1)] = [log26] = 3 < (Cs) = 4. But Cs is not set-semigraceful even if 2? < 
|E(Cs)| < 24—1 holds. Further as a consequence of the above theorem we have the graphs 
Ce U3Ky, C5 U4Kky and Cs U 2K are not set-semigraceful. 


Remark 3.9 By Theorem 2.5, for any subgraph G’ of G, y(G’) < 7(G). But subgraphs of 
a set-semigraceful graph need not be set-semigraceful. For example Kg is set-semigraceful but 
the spanning subgraph Cg of Kg is not set-semigraceful, by Theorem 2.19. 


In fact the result given by Theorem 3.3 holds for any set-semigraceful graph as we see in 
the following. 


Theorem 3.10 Every connected set-semigraceful (p,p — 1)-graph is a tree such that 
gm-1 4 1 Ke D < gm 
and for every m, such a tree always exists. 


Proof Clearly every connected (p,p— 1) graph T is a tree and by Theorem 3.3 we have 
2™-l11<p< 2” if T is set-semigraceful. On the other hand, for a given m, the star graph 














Kj ,2m_ 1 is set-semigraceful. 
Theorem 3.11 Jf the complete graph Ky; n > 2 is set-semigraceful then 


2m—1<7(Kn) <2m+1, where, m= |logon|. 


Proof If Ky is set-semigraceful then 


fio +1] = UK») > [tom | 


[logon + loge(n — 1) — loge2] 


I 





I 


[logon + logg(n —1)— 1]. 


For any n, there exists m such that 2™ <n < 2™*!— 1 so that from above y(K,) > 2m —1. 
But we have 


n(n —1)+2 


1) = flon®&=2 44] = fia 222] om 


64 Ullas Thomas and Sunil C. Mathew 











Thus we have 2m — 1 < 7(Kpn) < 2m+1; m= |logan|). 





Remark 3.12 The converse of Theorem 3.11 is not always true. For example, by Theorem 
2.20 we have 


2 |logon| — 1 < y(Kg) < 2 |logan| +1. 


But the complete graph Kg is not set-semigraceful. Also by Theorems 2.20 and 3.11 we have 
ky3, Ky4 and Ky5 are not set-semigraceful. 


Theorem 3.13 If a (p,q)-graph G has a set-semigraceful labeling with respect to a set X of 
cardinality m > 2, there exists a partition of the vertex set V(G) into two nonempty sets V, and 


V2 such that the number of edges joining the vertices of Vi with those of V2 is at most 2™—!. 


Proof Let f : VUE — 2* be a set-semigraceful labeling of G with indexing set X of 
cardinality m. Let Vi = {u € V : |f(u)| is odd} and V2 = V—Vy. We have |A @ B| = 
|A| + |B| — 2|A/N B| for any two subsets A, B of X and hence |A @ B| = 1(mod 2) > A and 
B does not belong to the same set Vj; 7 = 1,2. Therefore all odd cardinality subsets of X in 
f(£) must appear on edges joining V; and V2. Consequently there exists at most 2”~! edges 
between V; and V3. 














Remark 3.14 In 1986, B.D.Acharya [1] conjectured that the cycle Cgn_1; n > 2 is set-graceful 
and in 1989, Mollard and Payan [9] settled this in the affirmative. The idea of their proof is 
the following: 


Consider the field GF(2”) constructed by a binary primitive polynomial say p(a) of degree 
n. Let a be a root of p(x) in GF(2"). Then GF(2") = {0,1,a,a7,...,a2"~?}. Now by 
assigning a’~!mod p(a), 1 < i < 2"—1, to the vertices v; of the cycle Cgn_1 = (v1,...,Van_1, 1) 
we get a set-graceful labeling of Cyn_1 with indexing set X = {1,a,a?,...,a@”~!}. Note that 
here aJmod p(a) = apa® + ayat +...+@n_10"1; a; = 0 or 1 for 0 <i <n-1 with a® =1 
and we identify it as {aja’/ a; = 1; 0 <i<n-—1} which is a subset of X. 


Theorem 3.15 All cycles Cy with 2" -1<k <2"+2"-!—2,n>3 are set-semigraceful. 


Proof The cycle Cgn_1 = (v1, v2,°++ ,Von—1, 01) has a set-graceful labeling f as described 
in the above Remark 3.14. Take 1 = 2”~! — 1 new vertices u1,---,u,; and form the cycle 
Conqi-1 = (U1, U1, V2, U3, U2, V4, US, UZ, U6, U7, °° * » Von—3, Ul, Van—2, Von-1, U1). Now define a set- 
indexer g of Cgn4,-1 with indexing set Y = X U {x} as follows: g(u;) = f(vi); 1 <i < 2"-1 
and g(u;) = f(vaj-1, v2;) U {x}; 1 < 7 <1. Then by Theorem 2.4 we have y(C2n4;-1) =n +1. 
Now by removing the vertices u;; 2 < 7 < 1 and joining v2;_1v2; in succession we get the cycles 
Con41~-2, Con41-3,...,Con. Clearly g induces optimal set-indexers for these cycles by Theorem 
2.4 and 7(C,) =n +1; 2% <k < 2”+1-—2 so that these cycles are set-semigraceful. 














Theorem 3.16 The set-indexing number of the twing graph obtained from Pan_1 isn+2;n > 3 


and hence it is set-semigraceful. 


Proof Let Pan_1 = (v1,...,Van-1). By Theorem 2.10 we have y(Pon_1) =n. Let f be 


On Set-Semigraceful Graphs 65 


an optimal set-indexer of Pan_1 with indexing set X. Let T be a twing graph obtained from 
Pyn_1 by joining each vertex v;; i € {2,3,---,2” — 2} of Pon_, to two new vertices say u; and 
w; by pendant edges. Consider the set-indexer g of T with indexing set Y = X U {x, y} defined 
as follows: g(v) = f(v) for all v © V(Pan_1), g(us) = f(wi-1) U {x} and g(w;) = f(ui-1) U {y}; 
2<i< 2"—2. Consequently 7(T) <n-+2. But by Theorem 2.4 we have 





[loge(|E(T)| + 1)] = floge(2” —2+2"-342"-341)]) =n4+2< (1). 











Thus T is set-semigraceful. 





§4. Construction of Set-Semigraceful Graphs 


In this section we construct more set-semigraceful graphs from given ones through various graph 


theoretic methods. 


Theorem 4.1 Every set-semigraceful (p,q)-graph G with 7(G) = m can be embedded in a 
set-semigraceful (2™, q)-graph. 


Proof Let f be a set-semigraceful labeling of G with indexing set X of cardinality m = 
¥(G). Now add 2™ — p isolated vertices to G and assign the unassigned subsets of X under f 














to these vertices in a one to one manner. Clearly the resulting graph is set-semigraceful. 


Theorem 4.2 A graph G is set-semigraceful with y(G) =m, then every subgraph H of G with 
2™-1 < |E(H)| < 2™—1 is also set-semigraceful. 


Proof Since every set-indexer of G is a set-indexer of H, the result follows from Theorem 














2.4. 


Corollary 4.3 All subgraphs G of the star Ky, is set-semigraceful with the same set-indexing 
number m if and only if 2™-* < |E(G)| < 2™—-1. 











Proof The proof follows from Theorems 4.2 and 2.9. 





Theorem 4.4 Jf a (p,p—1)-graph G is set-semigraceful, then GV Non_, is set-semigraceful. 
Proof Let G be set-semigraceful with set-indexing number m. By Theorem 2.4 we have 


V(GV Noni) 2  [loge(|E(GV Non-1)| + 1)] 
[logo(p —1+ p(2”— 1) +1)] 
[logop(2”)] = [loge (2”) + loga(p)| = n+m. 


I 





l| 


Let f be a set-semigraceful labeling of G with indexing set X of cardinality m. Consider the 
set Y = {yi,.--,Yn} and let V(Non_1) = {v1,..., Un}. We can find a set-semigraceful labeling 
say g of GV Non_1 with indexing set X UY as follows: g(u) = f(u) for all u € V(G) and assign 
the distinct nonempty subsets of Y to the vertices v1,...,Un in any order. Thus GV Non_, is 











set-semigraceful. 





66 Ullas Thomas and Sunil C. Mathew 


Remark 4.5 The converse of Theorem 4.4 is not true in general. For example consider the 
wheel graph Ws = Cs V Ky = (ui, ue,...Us, ur) V {u}. Now assigning the subsets {a}, {a, bd}, 
{a,b,c}, {a,d}, {a,b,c,d} and ¢ of the set X = {a,b,c,d} to the vertices u1,...,us and u in 
that order we get Ws as set-semigraceful whereas C's is not set-semigraceful by Theorem 2.14. 


Corollary 4.6 The triangular book Kz V Ngn_, is set-semigraceful. 





Proof The proof follows from Theorems 4.4 and 2.10. 











Theorem 4.7 The fan graph F,, is set-semigraceful if and only ifn A 2™+1; n> 4. 


Proof Ifn—1 #2, by Theorem 2.10 we have P,,_1 is set-semigraceful so that by Theorem 
4.4, F,, = Pr_1 V Ky is set-semigraceful. 
Conversely if F;, is set-semigraceful, then by Theorem 3.3, we have 


V(Fr) = [loge(n —1+n—2+4+1)] = [loge(2n — 2)] = [loge(n —1)] +1. 


But by Theorem 2.17 we already have y(F;,) = [logon] + 1. Consequently we must have 
nA~2™ +1. 














Theorem 4.8 Every graph can be embedded as an induced subgraph of a connected set- 


semigraceful graph. 


Proof Let {v1,...,Un} be the vertex set of the given graph G. Now take a new vertex 
say u and join it with all the vertices of G. Consider the set X = {a1,...,a%,}. Let m = 
2” — (|E| +n) —1. Take m new vertices u4,...,tm and join them with wu. A set-indexer of the 
resulting graph G’ can be defined as follows: Assign ¢ to u and {x;} to vj; 1 <i <n. Let 
S={f(e): e€ E}U {{ai}: 1<i<n}. Note that |S| = |E£|+ 7. Now by assigning the m 
elements of 2* — (SU @) to the vertices u1,...,tm in any order we get a set-indexer of G’ with 











X as the indexing set, making G’ set-semigraceful. 





Theorem 4.9 The splitting graph S'(G) of a set-semigraceful bipartite (p,q)-graph G with 
7(G) =m and 3q > 2™*"1, is set-semigraceful. 


Proof Let f be an optimal set-indexer of G with indexing set X of cardinality m. Let 
Vi = {v1,...,Un} and V2 = {u1,...,uz} be the partition of V(G), where n = p—k. Since G 
is set-semigraceful with y(G) =m, by Theorem 3.3 we have 2™ 1! < q < 2™—1. To form the 


/ 
J 
joining v; or uj, to all neighbours of v; or u; in G respectively. Since S’(G) has 3q edges, by 


splitting graph S’(G) of G, for each v; or u; in G, add a new vertex v; or wu’, and add edges 


Theorem 2.4 we have 
7($'(G)) = [loga(|E(S'(G))| + 1)] = [loga(3q + 1)] = [loga(2""* + 1)] =m+2. 


We can define a set-indexer g of S’(G) with indexing set Y = X U {x,y} as follows: g(v) = f(v) 
for all v € V(G), g(v;) = flv) U {x}; 1 < i <n and g(uj) = f(us)U{y}s 1 <7 < L. 


Consequently 
+(S'(G)) =m +2 = [logs(|E($'(G))| + 1 


On Set-Semigraceful Graphs 67 











and hence $’(G) is set-semigraceful. 





Remark 4.10 (1) Even though C3 is not bipartite, both C3 and its splitting graph are set- 
semigraceful. 


(2) Splitting graph of a path P, is set-semigraceful. But P, is not set-semigraceful. 


Theorem 4.11 For any set-graceful graph G, the graph H; GU Ki CH CGV Ky, is set- 


semigraceful. 


Proof Let m = 7(G) = loga(|E(G)| + 1). Then by Theorem 2.4 we have 
YH) 2 [loge(|E(H)| + 1)] = [loga(2™ + 1)] = m+). 


Let f be a set-graceful labeling of G with indexing set X. Now we can extend f to a set-indexer 
g of GV Ky with indexing set Y = X U {x} of cardinality m+ 1 as follows: g(u) = f(u) for 
all u € V(G) and g(v) = {x} where {v} = V(G). Clearly g(e) = f(e) for all e € E(G) and 
g(uv) = g(u) U {a} are all distinct. Then by Theorem 2.5 we have 














(A) =m+1= [logs(|E(A)| +1). 


Corollary 4.12 The wheel Wan_, is set-semigraceful. 





Proof The proof follows from Theorems 4.11 and 2.30. 











Theorem 4.13 Let G be a set-graceful (p,p — 1)-graph, then GV Ny», is set-semigraceful. 


Proof Let G be set-graceful graph with set-indexing number n. For every m, there exists 
I such that 2! < m < 2'+1— 1. By Theorem 2.4 we have 


VGV Nm) 2 [log2(|E(GV Nm)| +1)] 
= [loge(p—1+ pm + 1)] = [logap(m + 1)] 
= [log2(2”)(m + 1)] = [log2(2”) + logo(m+1)] >n+ 141. 


Let f be a set-semigraceful labeling of G with X; |X| = n as the indexing set. Consider the set 
Y = {y,---, yi} and V(Nin) = {v1,...,Um}. Now we can extend f to GV N,, by assigning 
the distinct nonempty subsets of Y to the vertices v1, ..., Um in that order to get a set-indexer 
of GV N,, with indexing set X UY. Hence GV N,,, is set-semigraceful. 














Corollary 4.14 Ky,2n_1,m is set-semigraceful. 





Proof The proof follows from Theorems 2.33 and 4.13. 











Theorem 4.15 Let G be a (p,p — 1) set-graceful graph, then GV Ky and GV Kz are set- 


semigraceful. 


Proof Let f be a set-graceful labeling of G with indexing set X of cardinality n. By 


68 Ullas Thomas and Sunil C. Mathew 


Theorem 2.4 we have 


IV 


[loge (|E (GV K2)| + 1)] = [loge(p —1+2p+1+4+1)] 


1 
= [logo(3p+1)] = tos + loge(p + >| 
1 
= logs + logg(2” + >| >n+2. 


Consider the set Y = X U {&n41,%n+2} and the set-indexer g of GV K2 defined by g(u) = 
f(u) for all u € V(G), g(u1) = {an41} and g(v2) = {an+2}; v1, ve € V(K2). Consequently 
(GV Ko) =n+1 so that it is set-semigraceful. 

Let K3 = (v1, v2, 03,01). By Theorem 2.4 we have 7(G V K3) > [loga(|E(G V K3)| + 1)] 
=[loge(p —1+3p+3+41)] = [loge(4p + 3)] = [logo(4.2” + 3)] = [logo(2"t? +3)| > n+3. 
We can find a set-indexer h of GV Ks with indexing set Z = Y U {2,+3} as follows: Assign 
{tn+1}, {@n42} and {r,+3} to the vertices of K3 and h(u) = f(u) for all ue V(G). Clearly h 
is a set-semigraceful labeling of GV K3. 














Corollary 4.16 All double fans Py V Ko;n 4 2™, m> 2 are set-semigraceful. 





Proof The proof follows from Theorems 4.15 and 2.10. 











Corollary 4.17 The graph Ky,9n_1 V Kg ts set-semigraceful. 





Proof The proof follows from Theorems 4.15 and 2.13. 











Theorem 4.18 If C;, is set-semigraceful, then the graph C,,V K2 is set-semigraceful. Moreover 
(Cn V Ko) =m+ 2, where 2™<n<2™+2™1_2 n>7. 














Proof The proof follows from Theorems 3.15 and 4.15. 


Theorem 4.19 Let G be a set-semigraceful (p,q)-graph with y(G) =m. If p > 2™ 1, then 
GV ky set-semigraceful. 


Proof By Theorem 3.3 we have 2™~! < |E(G)| < 2™ — 1. Since |V| > 2™~1, by Theorem 
2.4 we have (GV Ki) > [logo(|E| +1)] = m+1. Let f be a set-indexer of G with indexing 
set X of cardinality m = 7(G). Now we can define a set-indexer g of GV Ky; V(k1) = {vu} 
with indexing set Y = X U {2} as follows: g(u) = f(u) for all u € V(G) and g(v) = Y. This 


shows that GV K; is set-semigraceful. 














Corollary 4.20 If Cn is set-semigraceful, then Wm 1s also set-semigraceful. 





Proof The proof follows from Theorem 4.19. 











Corollary 4.21 W,, is set-semigraceful, where 2™+1<n<2™+2™-1_ 1], 














proof The proof follows from Theorem 3.15 and Corollary 4.20. 


On Set-Semigraceful Graphs 69 


Theorem 4.22 The gear graph of order 2n+1 with 2°-1<n< gm-l4gm-3) m > 3 is 
set-semigraceful. 





Proof The proof follows from Theorem 2.5 and Corollary 4.21. 











Theorem 4.23 Let G be a set-semigraceful hamiltonian (p,q)-graph with y(G) = m and 
p> 27-1, IfG’ is a graph obtained from G by joining a pendand vertex to each vertex of G, 
then G’ is set-semigraceful. 


Proof Let C = (v1, v2,-++,Un,v1) be a hamiltonian cycle in G. Let f be a set-indexer 
of G with 7(G) = m and X be the corresponding indexing set. Now take n new vertices 
vy 1 <i < mand let G’ = GU {ujyu;/ 1 < i < n}. By Theorem 2.4 we have 7(G’) > 
[log2(|E(G’)| + 1)] = m-+1. We can define a set-indexer g of G’ with indexing set Y = XU {x} 
as follows: g(u) = f(u) for all u € V(G), g(vi) = f(uivigr) U {x}; 1 <a <n with vnqi = v1. 
Clearly G’ is set-semigraceful. 














Corollary 4.24 IfC,, is set-semigraceful, then the sun-graph obtained from C, is set-semigraceful. 





Proof The proof follows from Theorem 4.23. 











Corollary 4.25 The sun-graph of order 2n;2™ <n <2™+4+2™—-1_2:m > 3 is set-semigraceful. 





Proof The proof follows from Theorem 3.15 and Corollary 4.24. 











References 


[1] B.D.Acharya, Set valuations of graphs and their applications, Proc. Sympos. on Optimiza- 
tion, Design of Experiments and Graph Theory, Indian Institute of Technology Bombay, 
1986, 231-238. 

[2] B.D.Acharya, Set indexers of a graph and set graceful graphs, Bull. Allahabad Math. Soc., 
16 (2001), 1-23. 

[3] B.D.Acharya, S.Arumugam and A.Rosa, Labelings of Discrete Structures and Applications, 
Narosa Publishing House, New Delhi, 2008. 

[4] R.Anitha and R.S.Lekshmi, N-sun decomposition of complete, complete-bipartite and 
some Harary graphs, International Journal of Computational and Mathematical Sciences, 
2(2008), 33-38. 

5] G.Chartrand and P.Zhang, Introduction to Graph Theory, Tata Mcgraw Hill, New Delhi, 

2005. 

6| J.A.Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics, 

13 (2010). 

7| S.M.Hegde, On set valuations of graphs, Nat. Acad. Sci. Letteres, 14 (1991), 181-182. 

8] A.Kirlangic, The repture degree and gear graphs, Bull. Malays. Math. Sci. Soc., 32 

(2009), 31-36. 

9] M.Mollard and C.Payan, On two conjectures about set-graceful graphs, European J. Com- 








70 


10 


11 


12 


13 


14 


15 


16 





17 





Ullas Thomas and Sunil C. Mathew 


binatorics 10 (1989), 185-187. 

K.L.Princy, Some Studies on Set Valuations of Graphs-Embedding and NP Completeness, 
Ph.D. Thesis, Kannur University, 2007. 

W.C.Shiu and P.C.B.Lam, Super-edge-graceful labelings of multi-level wheel graphs, fan 
graphs and actinia graphs, Congr. Numerantium, 174 (2005), 49-63. 

U.Thomas and S.C.Mathew, On set indexers of multi-partite graphs, STARS: Int. Journal 
(Sciences), 3 (2009), 1-10. 

U.Thomas and $.C.Mathew, On set indexer number of complete k-partite graphs, Int. J. 
Math. Computation, 5 (2009), 18-28. 

U.Thomas and S.C.Mathew, On topological set indexers of graphs, Advances and Applica- 
tions in Discrete Mathematics, 5 (2010), 115-130. 

U. Thomas and S. C. Mathew, On set indexers of paths, cycles and certain related graphs, 
Discrete Mathematics, Algorithms and Applications (Accepted). 





U.Thomas and $.C.Mathew, Topologically set graceful stars, paths and related graphs, 
South Asian Journal of Mathematics (Accepted). 

T.M.Wang and C.C.Hsiao, New constructions of antimagic graph labeling, Proc. 24th 
Workshop on Combinatorial Mathematics and Computation Theory, National Chi Nan 
University Taiwan, 2007, 267-272. 


Math.Combin. Book Ser. Vol.2(2012), 71-75 


On Generalized m-Power Matrices and Transformations 


Suhua Ye!?, Yizhi Chen! and Hui Luo! 


1. Department of Mathematics, Huizhou University, Huizhou 516007, P.R.China 


2. School of Mathematical Science, South China Normal University, Guangzhou 510631, P.R.China 
E-mail: yizhichen1980@126.com 


Abstract: In this paper, generalized m—power matrices and generalized m—power trans- 
formations are defined and studied. First, we give two equivalent characterizations of gen- 
eralized m—power matrices, and extend the corresponding results about m— idempotent 
matrices and m—unit-ponent matrices. And then, we also generalize the relative results of 


generalized m—power matrices to the ones of generalized m—power transformations. 


Key Words: Generalized m—power matrix, generalized m—power transformation, equiv- 


alent characterization. 


AMS(2010): 15A24 


§1. Introduction 


The m-idempotent matrices and m—unit-ponent matrices are two typical matrices and have 
many interesting properties (for example, see [1]-[5]). 

A matrix A € C”*” is called an m—idempotent (m—unit-ponent) matrix if there exists 
positive integer m such that A™ = A(A™ = I). Notice that 


A™ = A if and only if [[(A+eil) =O, 


i=l 


where €; = 0, €2,€3,°-* ,Em are the m— 1 power unit roots, 


A™ = 1 if and only if [[(A+eil) =O, 


i=1 
where €1, €2,°°*,€m are the m—power unit roots. Naturally, we will consider the class of 
matrices which satisfies that 
m 
[[4+4) =o, 
i=1 
where \j, A2,°-: ,Am are the pairwise different complex numbers. 


lSupported by Grants of National Natural Science Foundation of China (No.11101174); Natural Science 
Foundation of Guangdong Province (No.S2011040003984); Natural Science Foundation of Huizhou University 
(C211 - 0106); Key Discipline Foundation of Huizhou University. 

2Received February 27, 2012. Accepted June 16, 2012. 


72 Suhua Ye, Yizhi Chen and Hui Luo 


For convenience, we call a matrix A € C”*” to be a generalized m—power matrix if it 
satisfies that [Jj ,(A + AZ) = O, where 1, A2,--- ,Am are the pairwise different complex 
numbers. 

In this paper, we firstly study the generalized m—power matrices, and give two equiv- 
alent characterizations of such matrices. Consequently, the corresponding results about m— 
idempotent matrices and m—unit-ponent matrices are generalized. And then, we also define 
the generalized m—power transformations, and generalize the relative results of generalized 
m-—power matrices to those of generalized m—power transformations. 

For terminologies and notations occurred but not mentioned in this paper, the readers are 
referred to the reference [6]. 


§2. Generalized m—Power Matrices 


In this section, we are going to study some equivalent characterizations of generalized m—power 


matrices. First, we introduce some lemmas following. 


Lemma 2.1([4]) Let A1,A2,--: ,Am be the pairwise different complez numbers and A € C"*". 
Then - a 

r([[(A+A2)) = So r(A+ AD) - (m= 1)n. 

i=l i=1 


Lemma 2.2((4]) Let fi(x), fa(x),--+,fm(x) € Cla] be pairwisely co-prime and A € C™*". 
Then 


m 


Yo r(f(A)) = (m= 1)n-4 eFC). 
Lemma 2.3([1]) Assume that f(x), g(a) € C[x], d(x) = (f(x), g(x)) and m(A) = [f (x), g(a)]. 
Then for any AE C"*", 


(f(A) + r(g(A)) = r(d(A)) + r(m(A)). 


Theorem 2.4 Let X41, 2,°°: ,Am € C be the pairwise different complex numbers and A € C"*". 
Then |], (A+ AL) = O if and only if i r(A+ AL) = (m= 1)n. 


Proof Assume that JT}, (A+A:iJ) = O, by Lemma 2.1, we can immediately get 07", r(A+ 
Ail) = (m— 1)n. 

Assume that )7/", r(A + AZ) = (m—1)n. Take fi(z) = «+ Ai(i = 1,2,--- ,m), where 
Ni FA; if 4 AJ. Clearly, we have (f;(x), f;(a)) =1ifi #7. Now, by Lemma 2.2, 


m m 


do r(Fi(A)) = (m — 1m + r(T] (F(A). 


i=l i=l 


Also, since >)", r(A + AL) = (m— 1)n, we can get r([] i, (fi(A))) = 0, this implies that 














Ue +A,2) =O. 


i=l 


Generalized m-Power Matrices and Generalized m-Power Transformations 73 


By Theorem 2.4, we can obtain the following conclusions. Consequently, the corresponding 
result in [3] is generalized. 





Corollary 2.5 Let €1,€2,--+ ,€m—1 € C be the m—1 power unit roots and A € C"*". Then 
A™ =A if and only if r(A) + r(A-— e1l) + 7(A — 01) +--+ +r (A = emit) = (m— In. 
Corollary 2.6 Let €1,€2,:-:,&m € C be the m power unit roots and A € C"*". Then A™ =I 


if and only if r(A— e1I) + 7r(A — eof) +--+ + 7r(A = eml) = (m—1)n. 


Now, we give another equivalent characterizations of the generalized m—power matrices. 


Theorem 2.7 Let X41, 2,-°: ,Am € C be the pairwise different complex numbers and A € C"*", 
Then 

7 (m — 2)(m—1)n 

[ [44D =0 ff and only if SO r((A+AT)(A+A4D)) = eer vaca 

i=1 1<i<j<m 


Proof Assume that [Jj".,(A + Ai) =O. Then r([][j".,(A + AiL)) = 0. Notice that 


S> r((A+ Al)(A + A5J)) a5 er r((A+AI)(A + A;1)) 


1<i<j<m i=1 j=i+1 


and by Lemmas 2.2 and 2.3, it is not hard to get that 


Sor((A+ at)(A +240) = = ADa rq aso) 





= (m—2)-r(A+A,J), 





Sor(A+dat\(A jf) +r(At UD) =n+ (m—3)-r(A+ rol), 














a r((A+A3l)(A + Aj) +r(A+ AD) + r(A + Aol) = 2n + (m—4)-r(A+As]), 


> T((A + Am—21)(A + AzI)) + r(A+ AI) = (m—3)-n+r(At+Am-_2I), 


a. i=l 
m—2 
r((A+Am—12)(A + AmL)) + $5 r(A + AL) = (m—2)-n 
1=1 


Thus, we have 


y: r((A+AD)(A+A;D) = (m= 2)(m= Vn 


— 2 
1<i<j<m 


From the discussions above, we have 


S> r((AtAI)(A+AjD)) = (mtn =n + (m—1)-r(]](A+,2)). 


1<i<j<m i=1 


74 Suhua Ye, Yizhi Chen and Hui Luo 

















Hence, if 
—2 -1 
S> r((A+ AIA +51) = SSS 
1<i<j<m 
then Ps 
r([[(4 +X) = 0, 

i=1 
Le., 

[[44.4) =0. 

i=1 

By Theorem 2.7, we can get corollaries following. Also, the corresponding result in [3] is 

generalized. 
Corollary 2.8 Let €1,€2,:+:,€m—1 € C be the m—1 power unit roots and A € C”*". Then 
A™ = A if and only if r(A(A — e12)) +--+ + r(A(A = Emil) + 7r((A — e12)(A — eof) 4+ + 


r((A—e11)(A— em—11)) +--+ r((A — Em—21)(A — €m—11)) = mn 


Corollary 2.9 Let €,€2,---,ém € C be the m power unit roots and AE C"*". Then A" =I 


if and only if 
ae r((A+eJ)(A+e,1)) = fue 


1<i<j<m 


§3. Generalized m—Power Transformations 


In this section, analogous with the discussions of the generalized m—power matrices, we will 
firstly introduce the concepts of generalized m—power linear transformations, and then study 
some of their properties. 

Let V be a n dimensional vector space over a field F' and o a linear transformation on V. 
We call o to be a generalized m—power transformation if it satisfies that 


m 


IIe + Vie) =@ 


i=1 
for pairwise different complex numbers j, A2,:-: ,Am, where € is the identical transformation 
and @ is the null transformation. Especially, o is called an m—idempotent ( m—unit-ponent) 
transformation if it satisfies that 0™ = o(o™ =). 

From [6], it is known that n dimensional vector space V over a field F’ is isomorphic to 
F” and the linear transformation space L(V) is isomorphic to F”*". Thus, we can obtain the 
following results about generalized m—power transformations whose proofs are similar with the 


corresponding ones in Section 2. And we omit them here. 


Theorem 3.1 Let V be an dimensional vector space over a field F and o a linear transfor- 


mation on V. Then o is a generalized m—power transformation if and only if 


3 dimIm(o + Axe) = (mM — 1)n. 


i=l 


Generalized m-Power Matrices and Generalized m-Power Transformations 75 


By Theorem 3.1, we obtain the following conclusions. 


Corollary 3.2 Let V be an dimensional vector space over a field F and o a linear transfor- 


mation on V. Then o is an m— idempotent transformation if and only if 
dimIm(A) + dimIm(A — 611) + dimIm(A — e921) +--+ + dimIm(A — €m_il) = (m — I)n. 


Corollary 3.3 Let V be an dimensional vector space over a field F and o a linear transfor- 


mation on V. Then o is an m—unit-ponent transformation if and only if 
dimIm(A — e,1) + dimIm(A — eof) +--- + dimIm(A — émI) = (m—1)n. 


Corollary 4.4 Let V be an dimensional vector space over a field F and o a linear transfor- 
mation on V. Then o is a generalized m—power transformation if and only if 
(m — 2)(m—1)n 


S- dimIm((a + Ax€)(o + Aje)) = ; 


1<i<j<m 
Corollary 3.5 Let V be an dimensional vector space over a field F and o a linear transfor- 


mation on V. Then o is an m— idempotent transformation if and only if 


dimIm(a(o — €1€)) +--+ + dimIm(o(o — €m_1€)) 

+dimIm(o — €1€)(o — €2€)) +--+ dimIm((o — e1€)(o — Em_1€)) 
—2 -1 

+-+++4+dimIm((o — €m—2€)(o — Em_-1€)) = —— 

Corollary 3.6 Let V be an dimensional vector space over a field F and o a linear transfor- 

mation on V. Then o is an m—unit-ponent transformation if and only if 

(m — 2)(m—1)n 


S- dimIm((o + ex€)(o + €5€)) = : 


1<i<j<m 


References 


1] G.Q.Lin, Z.P.Yang, M.X.Chen, A rank identity of matrix polynomial and its application, 
Journal of Bethua University (Natural science), 9(1)(2008),5-8. 

2| H.B.Qiu, Rank identities of a class of matrices, Journal of Guangdong University of Tech- 
nology, 24(1)(2007), 82-84. 

3] J.G.Tang, Q.Y.Yan, Necessary and sufficient conditions for unit-ponent matrices, Mathe- 
matics in Practice and Theory, 40(20)(2009),172-176. 

4) T.T.Wang, B.T.Li, Proof of a class of matrix rank identities, Journal of Shandong Univer- 
sity (Natural Science), 42(2)(2007), 43-45. 

5] Z.P.Yang, Z.X.Lin, An identity of the rank about the idempotent matrix and its application, 
Journal of Beihua University (Natural science) ,23(2)(2007),141-146. 

6] H.R.Zhang and B.X.Hao, Higher Algebra (In Chinese, the 5th edition), Higher Education 
Press, Beijing, 1999. 








Math.Combin. Book Ser. Vol.2(2012), 76-80 


Perfect Domination Excellent Trees 


Sharada B. 


(Department of Studies in Computer Science, University of Mysore, Manasagangothri, Mysore-570006, India) 
E-mail: sharadab21@gmail.com 


Abstract: A set D of vertices of a graph G is a perfect dominating set if every vertex in 
V \ D is adjacent to exactly one vertex in D. In this paper we introduce the concept of 
perfect domination excellent graph as a graph in which every vertex belongs to some perfect 
dominating set of minimum cardinality. We also provide a constructive characterization of 


perfect domination excellent trees. 


Key Words: Tree, perfect domination, Smarandachely k-dominating set, Smarandachely 


k-domination number. 


AMS(2010): 05C69 


§1. Introduction 


Let G = (V, EF) be a graph. A set D of vertices is a perfect dominating set if every vertex in 
V \ D is adjacent to exactly one vertex in D. The perfect domination number of G, denoted 
Yp(G), is the minimum cardinality of a perfect dominating set of G. A perfect dominating set 
of cardinality y,)(G) is called a 7p(G)-set. Generally, a set of vertices S in a graph G is said 
to be a Smarandachely k-dominating set if each vertex of G is dominated by at least k vertices 
of S and the Smarandachely k-domination number ¥,(G) of G is the minimum cardinality of a 
Smarandachely k-dominating set of G. Particularly, if k = 1, such a set is called a dominating 
set of G and the Smarandachely 1-domination number of G is nothing but the domination 
number of G and denoted by 7(G). Domination and its parameters are well studied in graph 
theory. For a survey on this subject one can go through the two books by Haynes et al [3,4]. 

Sumner [7] defined a graph to be y— excellent if every vertex is in some minimum dominat- 
ing set. Also, he has characterized y — excellent trees. Similar to this concept, Fricke et al [2] 
defined a graph to be i — excellent if every vertex is in some minimum independent dominating 
set. The i-excellent trees have been characterized by Haynes et al [5]. Fricke et al [2] defined 
yz — excellent graph as a graph in which every vertex is in some minimum total dominating 
set. The 7-excellent trees have been characterized by Henning [6]. 

In this paper we introduce the concept of yp-excellent graph. Also, we provide a construc- 
tive characterization of perfect domination excellent trees. 

We define the perfect domination number of G relative to the vertex u, denoted 7;/(G), as 
the minimum cardinality of a perfect dominating set of G that contains u. We call a perfect 
dominating set of cardinality 7,/(G) containing u to be a ¥(G)-set. We define a graph G to be 


1Received February 1, 2012. Accepted June 18, 2012. 


Perfect Domination Excellent Trees 77 


Yp — excellent if 7;;(G) = Yp(G) for every vertex u of G. 

All graphs considered in this paper are finite and simple. For definitions and notations not 
given here see [4]. A tree is an acyclic connected graph. A leaf of a tree is a vertex of degree 1. 
A support vertex is a vertex adjacent to a leaf. A strong support vertex is a support vertex that 
is adjacent to more than one leaf. 


§2. Perfect Domination Excellent Graph 


Proposition 2.1 A path P,, is yp) — excellent if and only ifn = 2 or n= 1(mod3). 


Proof It is easy to see that the paths P, and P,, for n = 1(mod3) are yp-excellent. Let 
P,,n > 3, be a yp-excellent path and suppose that n = 0, 2(mod3). If n = 0(mod3), then P,, 
has a unique Yp-set, which does not include all the vertices. If n = 2(mod3), then no yp-set of 











P,, contains the third vertex on the path. 





Proposition 2.2 Every graph is an induced subgraph of a yp)-excellent graph. 


Proof Consider a graph H and let G = Hok,, the 1-corona of a graph H. Every vertex in 
V (#) is now a support vertex in G. Therefore, V(#) is a yp-set of G. As well, the set of end 


vertices in G is a yp-set. Hence every vertex in V(G) is in some 7p-set and G is y,p-excellent. 











Since H is an induced subgraph of G, the result follows. 





§3. Characterization of Trees 


We now provide a constructive characterization of perfect domination excellent trees. We 
accomplish this by defining a family of labelled trees as defined in [1]. 

Let F = {Tr }n>1 be the family of trees constructed inductively such that T| is a path 
Py, and T,, = T, a tree. If n > 2, T;,1 can be obtained recursively from T; by one of the two 
operations F,, Fz fori =1,2,---,n—1. Then we say that T has length n in F. 

We define the status of a vertex v, denoted sta(v) to be A or B. Initially if T; = Py, then 
sta(v) = A if v is a support vertex and sta(v) = B, if v is a leaf. Once a vertex is assigned a 
status, this status remains unchanged as the tree is constructed. 


Operation 7, Assume y € T,, and sta(y) = A. The tree T,,41 is obtained from T,, by adding 
a path x, w and the edge xy. Let sta(x) = A and sta(w) = B. 





Operation F2 Assume y € T,, and sta(y) = B. The tree T,,41 is obtained from T,, by adding 
a path x, w,v and the edge xy. Let sta(x) = sta(w) = A and sta(v) = B. 


F is closed under the two operations F, and Fj. For T € F, let A(T) and B(T) be the 
sets of vertices of status A and B respectively. We have the following observation, which follow 
from the construction of F. 


Observation 3.1 Let T € F and v € V(T) 


78 Sharada B. 


1. If sta(v) = A, then v is adjacent to exactly one vertex of B(T) and at least one vertex of 
A(T). 


2. If sta(v) = B, then N(v) is a subset of A(T). 


3. If v is a support vertex, then sta(v) = A. 





4. If v is a leaf, then sta(v) = B. 
5. |A(T)| = |B(T)| 


6. Distance between any two vertices in B(T) is at least three. 


Lemma 3.2 IfT € F, then B(T) is a 7p(T)-set. Moreover if T is obtained from T' € F using 
operation F, or Fz, then yp(L) = yp(T") +1. 


Proof By Observation 3.1, it is clear that B(T) is a perfect dominating set. Now we 
prove that, B(T) is a 7p(T)-set. We proceed by induction on the length n of the sequence of 
trees needed to construct the tree 7. Suppose n = 1, then T = Fy, belongs to F. Let the 
vertices of P, be labeled as a,b,c,d. Then, B(P:) = {a, d} and is a yp(P1)-set. This establishes 
the base case. Assume then that the result holds for all trees in F that can be constructed 
from a sequence of fewer than n trees where n > 2. Let T € F be obtained from a sequence 
T,T2,--: , Tp of n trees, where T’ = T,,_-; and T = T,,. By our inductive hypothesis B(T’) is 
a Yp(T")-set. 

We now consider two possibilities depending on whether T is obtained from T” by operation 
Fy, or Fo. 


Case 1 T is obtained from T’ by operation F,. 


Suppose T is obtained from J” by adding a path y,z,w of length 2 to the attacher vertex 
y €V(Z"). Any y,(Z")-set can be extended to a yp(T)-set by adding to it the vertex w, which 
is of status B. Hence B(T) = B(T’) U {w} is a 7p(T)-set. 
Case 2 T is obtained from T’ by operation Fp. 


The proof is very similar to Case 1. 
If T is obtained from T’ € F using operation F; or Fo, then T can have exactly one more 
vertex with status B than T’. Since y,(T) = |B(T)| and y,(T") = |B(Z")|, it follows that 
Yp(T) = yp (T’) +1. 














Lemma 3.3 IfT € F have length n, then T is ay, — excellent tree. 


Proof Since T has length n in ¥, T can be obtained from a sequence 7,7 >,--- ,Tp, of 
trees such that T; is a path Py and T,, = T, a tree. If n > 2, T;,1 can be obtained from T; by 
one of the two operations F,, Fz fori = 1,2,--- ,n—1. To prove the desired result, we proceed 
by induction on the length n of the sequence of trees needed to construct the tree T’. 

Ifn = 1, then T’ = FP, and therefore, T is yp-excellent. Hence the lemma is true for the 


base case. 


Perfect Domination Excellent Trees 79 


Assume that the result holds for all trees in F of length less than n, where n > 2. Let 
T € F be obtained from a sequence T),7>,--- ,T, of n trees. For notational convenience, we 
denote T;,_1 by T’. We now consider two possibilities depending on whether T is obtained from 
T’ by operation Fy or Fo. 


Case 1 T is obtained from T’ by operation F,. 
By Lemma 3.2, y)(T') = yp(T’) + 1. Let wu be an arbitrary element of V(T). 
Subcase 1.1 ue V(T"). 


Since T” is yp-excellent, y;(T") = yp(T"). Now any 7; (7")-set can be extended to a perfect 
dominating set of T by adding either # or w and so f(T) < yp(T") + 1 = y(T") +1 = wp (7). 
Subcase 1.2 we V(T)\ V(T’). 

Any 7} (T")-set can be extended to a perfect dominating set of T by adding the vertex w 
and so 3 (T) < yg(7") +1 = %(T") +1 = (7). 

Consequently, we have 7;(T’) = y)(T) for any arbitrary vertex u of T. Hence T is 7p- 


excellent. 


Case 2 T is obtained from T’ by operation Fo. 











The proof is very similar to Case 1. 





Proposition 3.4 [fT is a tree obtained from a tree T’ by adding a path x,w or a path x,w,v 
and an edge joining x to the vertex y of T’, then y)(T) = yp(Z") +1. 


Proof Suppose T is a tree obtained from a tree T’ by adding a path z, w and an edge joining 
x to the vertex y of T’, then any y,(T’)-set can be extended to a perfect dominating set of T 
by adding x or w and so yp(T) < 7p(T’) +1. Now let S be a y,(T)-set and let S’ = SNV(Z"). 
Then S” is a perfect dominating set of T’. Hence, y,(T") < |S’| < |S|-—1=7)(T) — 1. Thus, 
p(T) > p(T") +1. Hence 7)(T) = yp(T") +1. The other case can be proved on the same lines. 














Theorem 3.5 A tree T of ordern > 4 is yp — excellent if and only if T € F. 


Proof By Lemma 3.3, it is sufficient to prove that the condition is necessary. We proceed 
by induction on the order n of a 7Yp-excellent tree T. For n = 4, T = P, is yp-excellent and also 
it belongs to the family F. Assume that n > 5 and all yp-excellent trees with order less than 
n belong to F. Let T be a yp-excellent tree of order n. Let P : v1, v2,--+ , vp be a longest path 
in T. Obviously deg(v1) = deg(v,) = 1 and deg(v2) = deg(vg_1) = 2 and k > 5. We consider 
two possibilities. 


Case 1 v3 is a support vertex. 


Let T’ = T \ {v1, v2}. We prove that T’ is yp-excellent, that is for any u € T’, yp (T") = 
Yp(T"). Since u € T’ C T and T is yp-excellent, there exists a y/(T)-set such that yp(T) = 
Yp(T). Let S be a ¥5(T’) — set and S’= SN V(Z"). Then S" is a perfect dominating set of T’. 
Also, |S"| < |S] — 1 = 7%(T) — 1 = 7(T"), by Proposition 3.4. Since u € S$’, S" is a y}(T")-set 


80 Sharada B. 


such that 7;(Z") = p(T"). Thus T” is yp-excellent. Hence by the inductive hypothesis T’ € F, 
since |V(T")| < |V(T)|. The sta(v3) = A in T’, because v3 is a support vertex. Thus, T is 
obtained from T’ € F by the operation F,. Hence T € F as desired. 


Case 2 v3 is not a support vertex. 


Let T’ = T \ {v1, v2, v3}. As in Case 1, we can prove that T’ is yp-excellent. Since 
|V(I")| < |V(T)|, T’ € F by the inductive hypothesis. 
If v4 is a support vertex or has a neighbor which is a support vertex then v3 is present in none 
of the yp-sets. So, T’ cannot be 7p-excellent. Hence either deg(vs) = 2 and v4 is a leaf of T’ so 
that v4 € B(T’) by Observation 3.1 or deg(v4) > 3 and all the neighbors of v4 in T’ \ {vs} are 
at distance exactly 2 from a leaf of T’. Hence all the neighbors of v4 in T’ \ {vs} are in A(T’) 
by Observation 3.1, and have no neighbors in B(T’) except v4. Hence v4 € B(T’), again by 
Observation 3.1. Thus, T can be obtained from T’ by the operation F2. Hence T € F. 














References 


1] H.Aram, S.M.Sheikholeslami and O.Favaron, Domination subdivision numbers of trees, 
Discrete Math., 309 (2009), 622-628. 

2] G.H.Fricke, T.W.Haynes, S.S.Hedetniemi and R.C.Laskar, Excellent trees, Bulletin of ICA, 
34(2002) 27-38. 

3] T.W.Haynes, S.T.Hedetniemi and P.J.Slater (Eds.), Domination in Graphs: Advanced Top- 
ics, Marcel Dekker, New York, 1998. 

4] T.W.Haynes, S.T.Hedetniemi and P.J.Slater, Fundamentals of Domination in Graphs, 
Marcel Dekker, New York, 1998. 

5| T.W.Haynes, M.A.Henning, A characterization of i-excellent trees, Discrete Math., 248 
(2002), 69-77. 

6] M.A.Henning, Total domination excellent trees, Discrete Math., 263(2003), 93-104. 

7| D.Sumner, personal communication, May 2000. 








Math. Combin. Book Ser. Vol.2(2012), 81-88 


On (k,d)-Maximum Indexable Graphs and 
(k,d)-Maximum Arithmetic Graphs 


Zeynab Khoshbakht 


Department of Studies in Mathematics 


University of Mysore, Manasagangothri MYSORE - 570 006, India 


E-mail: znbkht@gmail.com 


Abstract: A (n,m) graph G is said to be (k,d) maximum indexable graph, if its vertices 
can be assigned distinct integers 0,1,2,--- ,2—1, so that the values of the edges, obtained 
as the sum of the numbers assigned to their end vertices and maximum of them can be 
arranged in the arithmetic progression k,k + 1,k + 2d,--- ,k+(m-—1)d and also a (n,m) 
graph G is said to be (k,d) maximum arithmetic graph, if its vertices can be assigned distinct 
non negative integers so that the values of the edges, obtained as the sum of the numbers 
assigned to their end vertices and maximum of them can be arranged in the arithmetic 
progression k,k + 1,k + 2d,---,&+(m-—1)d. The energy E(G) of a graph G is equal to 
the sum of the absolute values of the eigenvalues of G. In this paper we introduce some 
families of graphs which are (k, d)- maximum indexable and (k, d)-maximum arithmetic and 


also compute energies of some of them. 


Key Words: Graph labeling, indexable graphs, (k, d)- Maximum indexable graphs, (k, d)- 


maximum arithmetic graphs. 


AMS(2010): 05078, 05050, 58040 


§1. Introduction 


Let G = (V, FE) be a (n,m) graph and let its vertex set be V(G) = {v1, v2,--+ , Un}. We assume 
that G is a finite, undirected, connected graph without loops or multiple edges. Graph labelings 
where the vertices are assigned values subject to certain conditions are interesting problems and 
have been motivated by practical problems. Applications of graph labeling have been found in 
X-— ray, crystallography, Coding theory, Radar, Circuit design, Astronomy and communication 
design. 

Given a graph G = (V,£), the set N of non-negative integers, a subset A of N of non- 
negative integers, a set A of N and a Commutative binary operation * : N x N — N 
every vertex function f : V(G) —> A induces an edge function f* : E(G) — N such that 
f*(uv) = *(f(u), f(v)) = flu) * fv), Vuu € E(G). We denote such induced map f* of f by 
fe 


1Received February 20, 2012. Accepted June 20, 2012. 


82 Zeynab Khoshbakht 


Acharya and Hedge [1,2] have introduced the concept of indexable and arithmetic graph 
labelings. Recently present author [7] has introduced the concept of maximum indexable graphs. 
The adjacency matrix A(G) of the graph G is a square matrix of order n whose (¢, j)-entry is 
equal to unity if the vertices v; and v; are adjacent, and is equal to zero otherwise. The 
eigenvalues \1,A2,::: ,An of A(G) are said to be the eigenvalues of the graph G, and are 
studied within the Spectral Graph Theory [3]. The energy of the graph G is defined as E = 
E(G) = SOy_, |Ai|.. The graph energy is an invariant much such studied in mathematical 
and mathema-tico-chemical literature; for details see [4,5,6], In this paper we introduce some 
families of graphs which are (k,d)- maximum indexable and (k,d)-maximum arithmetic and 
also compute energies of some of them. 


Definition 1.1 A graph G = (V,E) is said to be (k,d)— maximum indexable graph if it 
admits a (k,d)— indexer, namely an injective function f : V(G) —> {0,1,---,n—1} such 
that f(u) + f(v) + maaf{f(u), f(v)} = fmre"(uv) © f™r(G) = {f™*uv) : Vuv € E(G)} = 
{k,k+d,k+2d,---,k+(m-—1)d}, for every uw © E. 


Example 1.2 The graph K2,3 is a (4, 1)—maximum indexable graph. 


0 1 


Figure 1 


In this example, 
fP""(G) = {4,5, 6, 7, 8, 9}. 
Lemma 1.3 Let f be any (k,d)—mazimum indexable labeling of G. Then 


2<k<3n—md+ (d—4). 


Proof Since f™°*(G) C {2,3,--- ,38n—4}, the largest edge label is at most 3n — 4. Hence 
k must be less than or equal to 3n — 4— (m—1)d. Since the edge values are in the set 
{k,k+d,k+2d,---,k+(m-— 1)d}, we have 














2<k<3n—md+ (d—4). 


On (k, d)-Maximum Indexable Graphs and (k, d)-Maximum Arithmetic Graphs 83 


Theorem 1.4 The star Ky, is (k,d)—mazimum indexable if and only if (k,d) = (2,2) or 
(2n,1). Furthermore, there are exactly n +1 maximum indexable labelings of Ki, of which 


only two are (k,d)—maximum indexable up to isomorphism . 


Proof By assigning the value 0 to the central vertex and 1,2,3,---,n to the pendent ver- 
tices we get (2,2)—maximum indexable graph, since f™**(G) = {2,4,6,--- ,2n}. By assigning 
the value n to the root vertex and 0,1,2,--- ,n—1 to the pendent vertices, one can see that 
fm*(G) = {2n, 2n + 1,2n+3,--- ,3n—1}, which shows that G is (2n, 1)-maximum indexable 
graph. 

Conversely, if we assign the value c (0 < c < n) to the central vertex and 0,1,2,--- ,c—1,c+ 
1,--- ,n to the pendent vertices, we obtain f™* (Ay) = {2c, 2c+1,--+ ,3c—1,3c+2,--- ,2n+c} 
which is not an arithmetic progressive, i.e., Ky,» is not a (k,d)—maximum indexable. 

For the second part, note that K,,, is of order n+ 1 and size n. Since there are n+ 1 
vertices and n+ 1 numbers (from 0 to n), each vertex of Ay, can be labeled in n + 1 different 
ways. Observe that the root vertex is adjacent with all the pendent vertices. So if the root 
vertex is labeled using n + 1 numbers and the pendent vertices by the remaining numbers, 
definitely the sum of the labels of each pendent vertex with the label of root vertex, will be 
distinct in all n + 1 Maximum Indexable labelings of Ky,,. It follows from first part that, out 
of n + 1 maximum indexable labelings of Ky,,, only two are (k,d)—maximum indexable. This 











completes the proof. 





Corollary 1.5 The graph G = Ky ,U Kin, n> 1 is (k,d)—maximum indexable graph and its 
energy is equal to 4\/n — 1. 


Proof Let the graph G be Ki, U Kin, n > 1. Denote 

V(G) = {u1, U1; :1l<j< n} U {ua, v2; 21 <j< n}, 

E(G) = {urv1j : 1 <7 < n}U {ugve; :1 <j <n}. 
Define a function f : V(G) — {0,1,--- ,2n+1} by 

f(u1) =2n, f(ug) =2n-1 
F(v1j) = (27-1) and f(v2;) = 2G —- 1), 
for 7 = 1,2,---,n. Thus 
fP?*(Kan U Kin) = {4n4+ 1,40 4+ 2,4n + 3,-++ ,6n — 2,6n — 1, 6n}. 


Thus Ky, U Ky,» is (4n +1, 1)-maximum indexable graph. The eigenvalues of Ky, U Ky,» are 
+J/n—1,+Vn—1,0,0,---,0. Hence E(KinU Kin) =4/n—1. 
SS 


2n—4 times 




















Theorem 1.6 For any integer m > 2, the linear forest F = nP3U mP, is a (2m 4+ 2n,3) 


maximum indexable graph and its energy is 2(nV/2 +m). 


84 Zeynab Khoshbakht 


Proof Let F = nP3UmP, be a linear forest and V(F) = {ui,vi,wi : 1 <i < n}U 
{t;,yj : 1 <7 < m}. Then |V(F)| = 3n+ 2m and |E(F)| = 2n+™m. Define f : V(F) — 
{0,1,---,2m-+3n— 1} by 


i—1, y= Wi, 1l<i<n, 
m+tn+(i—1), y=uj, L<i<n, 
IOyH*. gn 1; y=, 1<j<m, 
2n+m)+(i-1), y=w, l<i<n 
Then 
PP"(F) = {2(n+m),2(n +m) + 3,2(m+n)+6--- ,2(m+n) + 


+3(n —1),5n + 2m,--- ,5n+ 5m — 3,5n + 5m, 8n + 5m — 3}. 


Therefore nP3 UmP3 is a (2(n + m),3)—maximum indexable graph. 


0 m+n 2n+2m 
e—______e+__e 


1 m+n+1 2n+2m+1 
o_________»—__———_ 
on m+2n-1 2m+3n-1 
o—___——-w————-e 
ti m+2n 
ee 
n+m-1 * 2n+2m-1 
o—__—__—_e 
Figure 2 


The eigenvalues of nP3 UU mP, are 1,-1 ,0, V2,—V2. Hence its energy is equal to E(nP3 U 
KH 


m times n times 








mP 2)) = 2(n/2+m). 








Corollary 1.7 For any integer m > 2, the linear forest F = P3UmPy is a (2m+2,3)—mazimum 
indexable graph. 





Proof Putting n = 1 in the above theorem we get the result. 











On (k, d)-Maximum Indexable Graphs and (k, d)-Maximum Arithmetic Graphs 85 


§2. (k,d)— Maximum Arithmetic Graphs 


We begin with the definition of (k,d)—maximum arithmetic graphs. 


Definition 2.1 Let N be the set of all non negative integers. For a non negative integer 
k and positive integer d, a (n,m) graph G = (V,E), a (k,d)—maximum arithmetic labeling 
is an injective mapping f : V(G) —> N, where the induced edge function f™* : E(G) — 
{k,k+d,k + 2d,--- ,k+(m—1)d} is also injective. If a graph G admits such a labeling then 
the graph G is called (k,d)—mazimum arithmetic. 


Example 2.2 Let $3 be the graph obtained from the star graph with n vertices by adding an 


edge. $@ is an example of (4,2)—maximum arithmetic graph. 
5 


Figure 3 S? 


Here 
fr (Sey 14.6.8, 10,12, 14). 


Definition 2.3 Let P, be the path on n vertices and its vertices be ordered successively as 
£1,22,°** ,2py. P! is the graph obtained from P,, by attaching exactly one pendent edge to each 


of the vertices 41, %2,°°: , 2X1. 
Theorem 2.4 P! is (k,d)—mazximum indexable graph. 


Proof We consider two cases. 


Case 1 If n is odd. In this case we label the vertices of P! as shown in the Figure . The value 
of edges can be written as arithmetic sequence {5,8,--- ,(3n—1), (8n + 2), (8n+5),--- ,(8n+ 
31 —1)}. It is clear that P! is (5,3)—maximum arithmetic for any odd n. 


(A) + 0-1) (3et1)41 anda 
2 
e——————_® 
n n—1 l I-1 2 1 


86 Zeynab Khoshbakht 


Case 2 If n is even. In this case we label the vertices of P! as shown in the Figure 5. The 

















value of edges can be written as arithmetic sequence {7, 13,--- ,(6n—5), (6n+1), (6n+7), (6n4 
13),--- ,(6n + 61 — 5)}. It is clear that P! is (7,6)— maximum arithmetic for any even n. 
o_ 
2n—1 2n—3 1-1 5 3 1 
Figure 5 


Theorem 2.5 The graph G = KoVKy_2 for n> 3 is a (10,2)— maximum arithmetic graph. 


Proof Let the vertices of K2 be v; and v2 and those of Ky,_2 be v3, v4,--+ , Un. By letting 
f(ui) = 2% for i = 1,2 and f(v;) = 22-1, 3 <i <n, we can easily arrange the values of edges 


of G = KoV K,,_2 in an increasing sequence {10,12,14,--- ,4n,4n + 2}. 














Lemma 2.6 The complete tripartite graph G = K12,n is a (7,1)—mazimum arithmetic graph. 


Proof Let the tripartite A, B, C be A = {w}, B = {v1, v2} and C = {v3,v4,--+ , Un}. 
Define the map f: AU BUC —N by 


Then one can see that G = Kj1,2, is (7,1)—maximum arithmetic. In fact f™*(Ki2n) = 
{7,8,9,10,--+,2n+5,2n+6,2n+7,--- ,3n+ 8}. 














Theorem 2.7 For positive integers m and n, the graph G = mK iy, is a (2mn + m+ 


2,1)—maximum arithmetic graph and its energy is 2mV/n— 1. 


Proof Let the graph G be the disjoint union of m stars. Denote V(G) = {uj:1<i< 
mbU{uy 2: 1<icmil<y <n} and E(G) = {uwy:1<i<m,l<j <n}. Define 
f:V(G) — N by 








f(z) = m(n+1)—-(i-1) ife=v; 1<i<m 


j}—1)m+i ifw@=uz; 1<i<m,1<j<n. 
G Jj ys bash 





Then 
fP?*(G) = {2mn + m + 2,2mn + m4 3,--- ,38mn+m+ 1h. 


Therefore mK, is a (2mn + m+ 2,1)—maximum arithmetic graph. 


On (k, d)-Maximum Indexable Graphs and (k, d)-Maximum Arithmetic Graphs 87 


U1 v2 Um 
Umn 
UW Um2 
U11 U12 Ulin a u22 U2n Um1 
Figure 6 





Also its eigenvalues are +\/n — 1 (m times). Hence the energy of mK1,,, is 











E(mKin) = 2mvVn— 1. 





§3. Algorithm 


In this section we present an algorithm which gives a method to constructs a maximum (k, d)- 


maximum indexable graphs. 
MATRIX-LABELING (Vlist,V size) 


//Vlist is list of the vertices, V size is number of vertices 
Elist= Empty(); 
for j < —0 to (Vsize —1) 
do for i < —0 to (Vlist —1) && i!=J 
X=V List[t] + Vlist[j] + Max {Viist[2], Vlist|j]}; 
if (Search (Elist, X)=False) —_//X does not exist in Elist 
then ADD (Elist, X); 
end if 
end for 
end for 
SORT-INCREASINGLY (Elist); 
Flag= 0; 
For j < —0 to (Esize — 1) 
do if (Elist[j + 1]! = Elist{j] + d) 
then Flag= 1; 
end if 
end for 


if (Flag== 0) 


88 


Zeynab Khoshbakht 


then PRINT (“This graph is a (k, d)—Max indexable graph” ); 
else if (Flag= 1) 
then PRINT (“This graph is not (&,d)—Max indexable graph” ); 
end if 
end MATRIX-LABELING(Vlist, V size) 


References 


1 








B.D.Acharya and S.M.Hegde, Strongly indexable graphs, Discrete Math., 93 (1991) 123- 
129. 

B.D.Acharya and S.M.Hegde, Arithmetic graphs, J.Graph Theory, 14(3) (1990), 275-299. 
D.Cvetkovié, M.Doob and H.Sachs, Spectra of Graphs- Theory and Application, Academic 
Press, New York, 1980. 

I.Gutman, The energy of a graph: Old and new results, in: A. Betten, A. Wassermann 
(Eds.), Algebraic Combinatorics and Applications, Springer Verlag, Berlin, (2001), 196-211. 
I.Gutman, Topology and stability of conjugated hydrocarbons. The dependence of total 
m—electron energy on molecular topology, J. Serb. Chem. Soc., 70 (2005), 441-456. 
I.Gutman and O.E.Polansky, Mathematical Concepts in organic Chemistry, Springer Ver- 
lag, Berlin, 1986. 

Z.Khoshbakht, On Maximum indexable graphs, Int. J. Contemp. Math. Sciences, Vol. 4, 
2009, no. 31, 1533-1540. 


Math.Combin. Book Ser. Vol.2(2012), 89-95 


Total Dominator Colorings in Paths 


A. Vijayalekshmi 
(S.T.Hindu College, Nagercoil, Tamil Nadu, India) 
E-mail: vijimath.a@gmail.com 


Abstract: Let G be a graph without isolated vertices. A total dominator coloring of a 
graph G is a proper coloring of the graph G with the extra property that every vertex in 
the graph G properly dominates a color class. The smallest number of colors for which there 
exists a total dominator coloring of G is called the total dominator chromatic number of G 
and is denoted by xza(G). In this paper we determine the total dominator chromatic number 


in paths. Unless otherwise specified, n denotes an integer greater than or equal to 2. 


Key Words: Total domination number, chromatic number and total dominator chromatic 
number, Smarandachely k-domination coloring, Smarandachely k-dominator chromatic num- 
ber. 


AMS(2010): 05C15, 05C69 


§1. Introduction 


All graphs considered in this paper are finite, undirected graphs and we follow standard defini- 
tions of graph theory as found in [2]. 

Let G = (V,E£) be a graph of order n with minimum degree at least one. The open 
neighborhood N(v) of a vertex v € V(G) consists of the set of all vertices adjacent to v. The 
closed neighborhood of v is N[v] = N(v) U {v}. For a set S C V, the open neighborhood N(S) 
is defined to be UyegN(v), and the closed neighborhood of S$ is N[S] = N(S)US. A subset S' of 
V is called a dominating (total dominating) set if every vertex in V — S (V) is adjacent to some 
vertex in S. A dominating (total dominating) set is minimal dominating (total dominating) set 
if no proper subset of S is a dominating (total dominating) set of G. The domination number 
y (total domination number 7) is the minimum cardinality taken over all minimal dominating 
(total dominating) sets of G. A +y-set (7-set) is any minimal dominating (total dominating) 
set with cardinality 7 (44). 

A proper coloring of G is an assignment of colors to the vertices of G, such that adjacent 
vertices have different colors. The smallest number of colors for which there exists a proper col- 
oring of G is called chromatic number of G and is denoted by x(G). Let V = {u1, wa, us,--- , Up} 
and C = {C, C2, C3,--- ,C,} be a collection of subsets C; C V. A color represented in a vertex 
u is called a non-repeated color if there exists one color class C; € C such that C; = {u}. 

Let G be a graph without isolated vertices. A total dominator coloring of a graph G is 


1Received September 19, 2011. Accepted June 22, 2012. 


90 A. Vijayalekshmi 


a proper coloring of the graph G with the extra property that every vertex in the graph G 
properly dominates a color class. The smallest number of colors for which there exists a total 
dominator coloring of G is called the total dominator chromatic number of G and is denoted by 
xXta(G). Generally, for an integer k > 1, a Smarandachely k-dominator coloring of G is a proper 
coloring on G such that every vertex in the graph G properly dominates a k color classes and 
the smallest number of colors for which there exists a Smarandachely k-dominator coloring of G 
is called the Smarandachely k-dominator chromatic number of G, denoted by xX2(G). Clearly, if 
k; = 1, such a Smarandachely 1-dominator coloring and Smarandachely 1-dominator chromatic 
number are nothing but the total dominator coloring and total dominator chromatic number 
of G. 


In this paper we determine total dominator chromatic number in paths. 


Throughout this paper, we use the following notations. 


Notation 1.1 Usually, the vertices of P,, are denoted by uj, u2,...,Un in order. We also denote 
a vertex uj © V(P,) with 1 > [$] by w_(n41). For example, un—1 by u_z. This helps us to 


visualize the position of the vertex more clearly. 


Notation 1.2 Fori < j, we use the notation ((7, j]) for the subpath induced by (uj, wit, ..., Uy)- 
For a given coloring C' of P,,, C|([t, j]) refers to the coloring C restricted to ([i, j]). 


We have the following theorem from [1]. 
Theorem 1.3 For any graph G with 6(G) > 1, max{y(G),7%4(G)} < xta(G) < x(G) + 74(G). 


Definition 1.4 We know from Theorem 1.3 that yta(Pn) © {ye(Pn), Ve(Pr) + 1, %4(Prn) + 2}- 
We call the integer n, good (respectively bad, very bad) if Xta(Pn) = Ye(Pn) +2 (if respectively 
Xta(Pr) = Ye(Pn) +1, xta(Pr) = Ye(Pr))- 


§2. Determination of yta(P,) 


First, we note the values of yta(P,,) for small n. Some of these values are computed in Theorems 
2.7, 2.8 and the remaining can be computed similarly. 





Total Dominator Colorings in Paths 91 





Thus n = 2,3,6 are very bad integers and we shall show that these are the only bad integers. 
First, we prove a result which shows that for large values of n, the behavior of x+a(P,) depends 
only on the residue class of nmod 4 [More precisely, if n is good, m > n and m = n(mod 4) 
then m is also good]. We then show that n = 8,13,15,22 are the least good integers in their 
respective residue classes. This therefore classifies the good integers. 


Fact 2.1 Let 1 <i<_nand let C be a td-coloring of P,. Then, if either u; has a repeated 
color or u;+2 has a non-repeated color, C|([¢ + 1,n]) is also a td-coloring. This fact is used 
extensively in this paper. 


Lemma 2.2) yta(Pni4) > xXta(Pn) + 2. 


Proof For 2 < n < 5, this is directly verified from the table. We may assume n > 6. 
Let uj, U2,U3,.--,Un+4 be the vertices of P,44 in order. Let C’ be a minimal td-coloring of 
Py+4. Clearly, ug and w_2 are non-repeated colors. First suppose u4 is a repeated color. Then 
C| ([5,n + 4]) is a td-coloring of P,. Further, C| ([1, 4]) contains at least two color classes of C. 
Thus xta(Pn + 4) > xvta(Pr) + 2. Similarly the result follows if u_4 is a repeated color Thus 
we may assume u4 and w_4 are non-repeated colors. But the C| ([3, + 2]) is a td-coloring and 














since Ug and u_»2 are non-repeated colors, we have in this case also xta(Pni4) > xta(Pn) + 2. 


Corollary 2.3 If for any n, xta(Pn) = ¥2(Pn) + 2, Xta(Pm) = ¥%4(Pmn) +2, for all m > n with 
m = n(mod 4). 











Proof By Lemma 2.2, xta(Pn+4) > Xta(Pn) + 2 = %(Pr) + 2+ 2 = %4(Pr4+a) + 2. 





Corollary 2.4 No integer n > 7 is a very bad integer. 


Proof For n = 7,8,9,10, this is verified from the table. The result then follows from the 
Lemma 2.2. 














Corollary 2.5 The integers 2,3,6 are the only very bad integers. 


Next, we show that n = 8,13,15,22 are good integers. In fact, we determine yta(P,,) for 
small integers and also all possible minimum td-colorings for such paths. These ideas are used 


more strongly in determination of yza(P,) for n = 8,13, 15, 22. 


Definition 2.6 Two td-colorings C, and C2 of a given graph G are said to be equivalent if 
there exists an automorphism f : G— G such that Co(v) = Ci(f(v)) for all vertices v of G. 


This is clearly an equivalence relation on the set of td-colorings of G. 


92 A. Vijayalekshmi 


Theorem 2.7 Let V(P,) = {u1, u2,...,Un} as usual. Then 

(1) Xta(P2) = 2. The only minimum td-coloring is (given by the color classes) {{u1}, {u2}} 
(2) xXta(P3) = 2. The only minimum td-coloring is {{ui,u3}, {ua}}. 

(3) xXta(P1) = 3 with unique minimum coloring {{u1, ua}, {uz}, {us}}. 


(4) xXta(P5) = 4. Any minimum coloring is equivalent to one of {{ui, us}, {ua}, {ua}, {us}} or 


{{u1, us}, {uz}, {us}; {ua}} or {{ui}, {ug}, {ua}, {us, us}}- 
(5) xXta(Ps) = 4 with unique minimum coloring {{u1, us}, {ua, ue}, {uz}, {us}}. 


(6) xta(P7) = 5. Any minimum coloring is equivalent to one of {{u1, us}, {uz}, {ua, uz}, {us}, 


{ue}} or {{u1, us}, {uz}, {us}, {us, ur}, {ue}} {{u1, Ua, ur}, {uz}, {us}, {us}, {ue}}- 


7 
Proof We prove only (vi). The rest are easy to prove. Now, %(P7) = [=] = 4. Clearly 


Xta(P7) > 4. We first show that x:q(P7) 4 4 Let C be a td-coloring of P; with 4 colors. The ver- 
tices ug and u_z2 = ug must have non-repeated colors. Suppose now that us has a repeated color. 
Then {ui, u2, ug} must contain two color classes and C| ([4,7]) must be a td-coloring which will 
require at least 3 new colors (by (3)). Hence w3 and similarly u_3 must be non-repeated colors. 
But, then we require more than 4 colors. Thus y+a(P7) = 5. Let C be a minimal td-coloring 
of P;. Let wz and u_2z have colors 1 and 2 respectively. Suppose that both uz and u_3 are 
non-repeated colors. Then, we have the coloring {{u1, w4, uz}, {uo}, {us}, {us}, {ue}}. If either 
ug or u_3 is a repeated color, then the coloring C’ can be verified to be equivalent to the coloring 


given by {{u1, us}, {ug}, {ua, uz}, {us}, {ue}}, or by {{u1, ua}, {uz}, {us}, {us, ur}, {ue}}- 


We next show that n = 8,13, 15,22 are good integers. 














Theorem 2.8 x¢a(Pn) = %(Pr) +2 ifn = 8, 13,15, 22. 


Proof As usual, we always adopt the convention V(P,,) = {u1,U2,...,Un};U-i = Un4i—i 
for i > lel C denotes a minimum td-coloring of Py. 


We have only to prove |C| > (Pn) +1. We consider the following four cases. 
Case l n=8 


Let |C| = 5. Then, as before uz, being the only vertex dominated by uz has a non-repeated 
color. The same argument is true for u_2 also. If now ug has a repeated color, {u1, u2, u3} 
contains 2-color classes. As C|([4, 8]) is a td-coloring, we require at least 4 more colors. Hence, 
ug and similarly u_3 must have non-repeated colors. Thus, there are 4 singleton color classes 
and {ug}, {u3}, {u-2} and {u_3}. The two adjacent vertices u4 and u_4 contribute two more 
colors. Thus |C| has to be 6. 


Case 2 n=13 


Let |C| = 8 = %(Pi3)+1. As before ug and u_2 are non-repeated colors. Since yta(Pio) = 
7+2 = 9, uz can not be a repeated color, arguing as in case (i). Thus, ug and u_3 are also non- 
repeated colors. Now, if u; and u_; have different colors, a diagonal of the color classes chosen 


Total Dominator Colorings in Paths 93 





as {u1, U-1, U2, U_2, U3, U_3,---} form a totally dominating set of cardinality 8 = y(Pi3) + 1. 
However, clearly u; and u_; can be omitted from this set without affecting total dominating 
set giving %(Pi3) < 6, a contradiction. Thus, u; and u_; = ui3 have the same color say 1. 
Thus, ({4,—4]) = ([4,10]) is colored with 4 colors including the repeated color 1. Now, each of 
the pair of vertices {w4, ue}, {us, u7}, {us, Wig} contains a color classes. Thus ug = u_5 must 
be colored with 1. Similarly, us. Now, if {u4, ug} is not a color class, the vertex with repeated 
color must be colored with 1 which is not possible, since an adjacent vertex us which also has 
color 1. Therefore {u4, ug} is a color class. Similarly {ug,wio} is also a color class. But then, 
uz will not dominate any color class. Thus |C| = 9. 


Case 3 n=15 


Let |C| = 9. Arguing as before, wz, u_2, ug and u_3 have non-repeated colors [V1a(Pi2) = 
8]; ui; and u_y have the same color, say 1. The section ([4,—4]) = ([4,12]) consisting of 9 
vertices is colored by 5 colors including the color 1. An argument similar to the one used in 
Case (2), gives u4 (and w_4) must have color 1. Thus, C| ([5, —5]) is a td-coloring with 4 colors 
including 1. Now, the possible minimum td-coloring of P7 are given by Theorem 2.7. We can 
check that 1 can not occur in any color class in any of the minimum colorings given. e.g. 
take the coloring given by {us, us}, {ue}, {uz}, {uo, wir}, {uo}. If ug has color 1, us can not 
dominate a color class. Since u4 has color 1, {us, ug} can not be color class 1 and so on. Thus 
Xtd(Pis) = 10. 


Case 4 n= 22 


Let |C| = %(Po2) + 1 = 13. We note that x1a(Pi9) = %4(Pi9) + 2 = 12. Then, arguing as 
in previous cases, we get the following facts. 


Fact 1 u2,u_—2, U3, u-3 have non-repeated colors. 
Fact 2 u; and u_, have the same color, say 1. 
Fact 3 wu7 is a non-repeated color. 


This follows from the facts, otherwise C| ([8,22]) will be a td-coloring; The section ([1, 7]) 
contain 4 color classes which together imply x+a(Po2) > 4+xX+ta(Pis) = 4+10 = 14. In particular 
{us, uz} is not a color class. 


Fact 4 The Facts 1 and 2, it follows that C| ({4,—4]) = C| ([4,19]) is colored with 9 colors 
including 1. Since each of the pair {{ua, uo}, {us, U7}, {us, io}, {uo, Wii, {ur2, Uist, {u13, Wis }, 
{u16, vis}, {u17, uig}} contain a color class, if any of these pairs is not a color class, one of the 
vertices must have a non-repeated color and the other colored with 1. From Fact 3, it then 
follows that the vertex us must be colored with 1. It follows that {u4, ug} must be a color class, 
since otherwise either u4 or ug must be colored with 1. 

Since {ua, ue} is a color class, u7 must dominate the color class {ug}. 


We summarize: 
© U2, U3, U7, Ug have non-repeated colors. 


e {u4, ue} is a color class 


94 A. Vijayalekshmi 


e wu; and us are colored with color 1. 
Similarly, 

© U_2,U_3, U_7, U_g have non-repeated colors. 

e {u_4, u_e} is a color class. 

e u_; and u_s are colored with color 1. 


Thus the section ([9, —9]) = ({9,14]) must be colored with 3 colors including 1. This is easily 
seen to be not possible, since for instance this will imply both ui3 and ui4 must be colored with 











colorl. Thus, we arrive at a contradiction. Thus yza(P22) = 14. 





Theorem 2.9 Let n be an integer. Then, 
(1) any integer of the form 4k, k > 2 is good; 
(2) any integer of the form 4k +1, k > 3 is good; 
(3) any integer of the form 4k + 2, k 
(4) any integer of the form 4k +3, k 


> 5 is good; 
> 3 is good. 














Proof The integers n = 2,3,6 are very bad and n = 4,5,7,9,10,11, 14, 18 are bad. 


Remark 2.10 Let C be a minimal td-coloring of G. We call a color class in C, a non-dominated 
color class (n-d color class) if it is not dominated by any vertex of G. These color classes are 
useful because we can add vertices to these color classes without affecting td-coloring. 


Lemma 2.11 Suppose n is a good number and P, has a minimal td-coloring in which there 
are two non-dominated color class. Then the same is true forn+A4 also. 


Proof Let C1, C2,...,C; be the color classes for P,, where C, and C2 are non-dominated 
color classes. Suppose u,, does not have color Cy. Then CyU{un+1}, CoU{unsa}, {Une}, {un+3}, 





C3, C4,--- ,C, are required color classes for P,+44. i.e. we add a section of 4 vertices with mid- 
dle vertices having non-repeated colors and end vertices having C, and C2 with the coloring 
being proper. Further, suppose the minimum coloring for P,,, the end vertices have different 
colors. Then the same is true for the coloring of P,,44 also. If the vertex u, of P,, does not have 
the color C2, the new coloring for P,44 has this property. If wu; has color C2, then u,, does not 
have the color C2. Therefore, we can take the first two color classes of Pr44 as Cy U {un+a} 
and C2 U {un41}. 














Corollary 2.12 Letn be a good number. Then P, has a minimal td-coloring in which the end 
vertices have different colors. [It can be verified that the conclusion of the corollary is true for 
alln 4 3,4,11 and 18]. 


Proof We claim that P, has a minimum td-coloring in which: (1)there are two non- 
dominated color classes; (2)the end vertices have different colors. 


n=8 
n=13 
n=15 
n = 22 


Now, it follows from the Lemma 2.11 that (1) and (2) are true for every good integer. O 


Total Dominator Colorings in Paths 95 








e 2 -2- -2- 2- 2- 2 2 nl 2 2 2 ad 
Ty T2 TL T2 TL r2 

e 2s 2s 2s a ad ad ad nd nd ad ad nd 
Ty T2771 T2 TI. T2 








Fig.1 





Corollary 2.13 Let n be a good integer. Then, there exists a minimum td-coloring for P, with 


two n-d color classes. 


References 








1] M.I. Jinnah and A.Vijayalekshmi, Total Dominator Colorings in Graphs, Ph.D Thesis, Uni- 
versity of Kerala, 2010. 

2| F.Harrary, Graph Theory, Addition - Wesley Reading Mass, 1969. 

3] Terasa W.Haynes, Stephen T.Hedetniemi, Peter J.Slater, Domination in Graphs, Marcel 
Dekker , New York, 1998. 

4] Terasa W.Haynes, Stephen T.Hedetniemi, Peter J.Slater, Domination in Graphs - Ad- 


vanced Topics, Marcel Dekker,New York, 1998. 


Math.Combin. Book Ser. Vol.2(2012), 96-102 


Degree Splitting Graph 
on Graceful, Felicitous and Elegant Labeling 


P.Selvaraju 1, P.Balaganesan?, J.Renuka ? and V.Balaj 4 


1. Department of Mathematics, Vel Tech Engineering College,Chennai- 600 062, Tamil Nadu, India 





2. Department of Mathematics, Saveetha School of Engineering, Saveetha University, 


Chennai- 602 105, Tamil Nadu, India 
3. Departments of Mathematics, Sai Ram College of Engineering, Chennai - 600 044, Tamil Nadu, India 


4. Department of Mathematics, Sacred Heart College(Autonomous) Tirupattur-635 601, 


Vellore(Dt), Tamil Nadu, India 
E-mail: balki2507@yahoo.co.in 


Abstract: We show that the degree splitting graphs of Bnjn; Pr; Kmjnj n(ka — 3e)I; n(ka — 
3e)I1(b); n(ka — e)IT and n(ka — 2e)II(a) are graceful [3]. We prove C30K1,n is graceful, 


felicitous and elegant [2], Also we prove K2,n is felicitous and elegant. 


Key Words: Degree splitting graph, graceful graph, elegant graph, felicitous graph, star 
and path. 


AMS(2010): 05C78 


§1. Introduction 


Graph labeling methods were introduced by Rosa in 1967 or one given by Graham and Sloane 
in 1980. For a graph G, the splitting graph S(G) is obtained from G by adding for each vertex 
v of G, a new vertex v’ so that vu’ is adjacent to every vertex in G. 

Let G be a graph with qg edges. A graceful labeling of G is an injection from the set of its 
vertices into the set {0,1,2,---q} such that the values of the edges are all the numbers from 
1 to q, the value of an edge being the absolute value of the difference between the numbers 
attributed to their end vertices. 

In 1981 Chang, Hiu and Rogers defined an elegant labeling of a graph G, with p vertices 
and q edges as an injective function from the vertices of G to the set {0,1,2,---q} such that 
when each edge xy is assigned by the label f(x) + f(y)(mod (q+ 1)), the resulting edge labels 
are distinct and non zero. Note that the elegant labeling is in contrast to the definition of a 
harmonious labeling [1]. 

Another generalization of harmonious labeling is felicitous labeling. An injective function 
f from the vertices of a graph G with q edges to the set {0,1,2,---q} is called felicitous labeling 
if the edge label induced by f(x) + f(y)(mod q) for each edge zy is distinct. 


1Received January 30, 2011. Accepted June 24, 2012. 


Degree Splitting Graph on Graceful, Felicitous and Elegant Labeling 97 


§2. Degree Splitting Graph DS(G) 


Definition 2.1 Let G = (V,E) be a graph with V = S$, U S2:U $3 U---S;UT where each S; is 
a set of vertices having at least two vertices of the same degree and T =V\US;. The degree 
splitting graph of G denoted by DS(G) is obtained from G by adding vertices w1, w2,W3,-+++ , We 
and joining to each vertex of S; for 1 <i<t. 


§3. Main Theorems 


Theorem 3.1 The DS(Bn.») ts graceful for n > 2. 


Proof Let G = By» be a graph.Let V(G) = {u,v,ui,u; : 1 <i <n} and V(DS(G)) \ 
V(G) = {wi, we}. Let E(DS(G)) = {uv, wwe, vwe} U {uui, vu;, wiui, Wi; 2 1 <i <n} and 
| E(DS(G)) |= 4n 4+ 3. 

The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,4n + 3} is as follows: 


f(u) =1; f(v) = 38; f(w1) = 0; f(we) = 2n + 4; f(us) = 4n — 21 +5 and f(v;) = 274 2 for 
l<i<n. 


The corresponding edge labels are as follows: 


The edge label of wv is 2; wu; is 4n — 204+ 4 for 1 <i <n; vv; is 2i-—1 for l <i<njs wy; 
is 4n — 214+ 5 for 1 <i < nj wiv; is 214+ 2 for 1 <i < nj uwe is 2n+ 3 and vwe is 2n + 1. 
Hence the induced edge labels of DS(G) are 4n + 3 distinct integers. Hence DS(G) is graceful 
for n > 2. 














Theorem 3.2 The DS(P,) is graceful for n > 4. 


Proof Let G = P, be a graph. Let V(G) = {v; : 1 <i < n} and V(DS(G)) \ V(G) = 
{wi, wa}. Let E(DS(G)) = {wivi, win} U {wovj : 2<4<n-—1} and | E(DS(G)) |= 2n-1. 
The required vertex labeling f : V(DS(G) — {0,1,2,--- ,2n— 1} is as follows: 


Case 1 nis odd. 


Then f(wi) =n+1; f(we) = 0; f(u) =i for 1<i<n, iis odd and f(v;) = 2n-i+1 for 
1<i<n, 7 is even. 


The corresponding edge labels are as follows: 


The edge label of wou; is i for 3 <1 <n-—1 and i is odd; wav; is 2n-i+1 forl<i<n 
and 7 is even; w V1 is nN; W1Vy, is 1 and v;V;41 is 2n — 2i for 1 <7 <n-—J1. Hence the induced 
edge labels of DS(G) are 2n — 1 distinct integers. Hence DS(G) for n > 4 is graceful. 


Case 2 n is even. 


The required vertex labeling is as follows: 


f(wi) = n+ 2; f(we) = 0; f(u;) = 7 for 1 <i < n,i is odd and f(u;) = 2n-i+1 for 


98 P.Selvaraju, P.Balaganesan, J.Renuka and V.Balaj 


1<i< 7,2 is even. 

The corresponding edge labels are as follows: 

The edge label of w2v,; is 7 for 3 <7 <n and 7 is odd; wou; is 2n-i+1 forl<i<n-1 
and 7 is even; w,v1 is N+1; win is 1 and v,vj41 is 2n—2 for 1 <<71<n-—1. Hence the induced 


edge labels of G are 2n — 1 distinct integers. From case (i) and (ii) the DS(P,,) for n > 4 is 


graceful. 














Theorem 3.3 The graph DS(Km.n) is graceful. 


Proof The proof is divided into two cases following. 
Case l m>n. 

Let G = Ky» be a graph. Let V(G) = {u;: 1 <i < mb}Uf{uj:1 <7 < n} and 
V(DS(G)) \ V(G) = {wi, we}. Let E(DS(G)) = {wus 1 <i < mb}Uf{wo:1<j< 
n}U {uivj :1<i<m,1<j <n} and | E(DS(G)) |=mn+m-+n. 

The required vertex labeling f : V(DS(G)) > {0,1,2,---,mn+m-+n} is as follows: 





f(u) = m(n+2-i)4+n for 1 <i < mf(v;) = 7 for 1 < 7 < n;f(wi) = 0 and 
f(w2) =n+1. 


The corresponding edge labels are as follows: 
The edge label of wi u; is m(n+2—1)+n for 1 <i< m;ujv; is mM(n+2—1)+n—j for 


1<icm1l<j<nand wov; isn+1—j for 1 <j <n. Hence the induced edge labels of G 
aremn+m-+n distinct integers. Hence the graph DS(K mn) is graceful. 





Case 2 m=n. 


Let G = Kmn be a graph Let V(G) = {wu : 1 < it < m} and 
V(DS(G))\ V(G) = {ui}. Let E(DS(G)) = {wiwi, wivi: 1<i< m}U {ujv; +1 < 14,7 < m} 
and | E(DS(G)) |= m(m + 2). 


The required vertex labeling f : V(DS(G)) — {0,1,2,--- ,m(m + 2)} is as follows: 
f(wi) = 0; f(us) = m(m + 3) — mi for 1 <i < mand f(v;) =i for 1<i<m. 
The corresponding edge labels are as follows: 


The edge label of wiv; is i for 1 < i < m;ujv; is mM(m+ 3) — mi — 7 for 1 < i,j < mand 
wu; is m(m+3)—mi for 1 <i <m. Hence the induced edge labels of G are m(m-+ 2) distinct 














integers. Hence the graph DS(Kym,n) is graceful. 


Corollary 3.4 The DS(K,,) is Ky41. 
Theorem 3.5 The DS(n(K4 — 3e)1)) is graceful. 


Proof Let G = n(K4 — 3e)I be a graph. Let V(G) = {a,y}U{z:1 <i < n} and 
V(DS(G)) \ V(G) = {wi, wo}. Let E(DS(G)) = {xwe, ywo, ry} U {wizi, v2, yz 1<i<n} 


Degree Splitting Graph on Graceful, Felicitous and Elegant Labeling 99 


and | E(DS(G)) |= 3n+3. 
The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,3n+ 3} is as follows: 


f(x) =1; fly) = 2; f(w1) = 0; f(we) = 4 and f(z;) = 3n + 6-37 for l<i<n. 
The corresponding edge labels are as follows: 


The edge label of ry is 1; rw is 3; ywe is 2; xz; is 8n+5— 31 for 1 <1 < nj yz; is 8n+4-—31 
for 1 <i <nand w,zZ; is 3n + 6 — 32 for 1 < i < n. Hence the induced edge labels of G are 
3n +3 distinct integers. Hence the DS(G) is graceful. 














Theorem 3.6 The DS((n(K4 — 3e)II(b)) is graceful. 


Proof Let G = n(K4 — 3e)II(b) be a graph. Let V(G) = {x,y} U {ui,u,: 1 <i <n} and 
V(DS(G)) \ V(G) = {w1, wo} Let E(DS(G)) = {aw1, cy} U {wij;, wii, yur, W2uj 2 1 <i <n} 
and | E(DS(G)) |= 4n+ 2. 

The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,4n + 2}is as follows: 


f(x) = 38n + 2; f(y) = 1; f(wi) = 0; f(we) = 2; fui) = 38n+2+7% for 1 <i < n and 
f(u;) = 20+ 1 forl<i<n. 


The corresponding edge labels are as follows: 


The edge label of w vu; is 8n+2+i7 for 1<i<njujv; is 8n—-—i4+1 for 1 <i< n;yu; is 22 
for 1 <i <n;weu; is 2i-—1 for 1 <i < nj rw, is 8n+ 2 and zy is 3n+ 1. Hence the induced 











edge labels of G are 4n + 2 distinct integers. Hence the graph DS(G) is graceful. 





Theorem 3.7 The DS(n(K4— e)II) is graceful. 


Proof Let G = n(K4 — e)ITI) be a graph. Let V(G) = {z,y} U {ui,u; : 1 <i < nm} and 
(DS(G)) \ V(G) = {w1, wo} Let E(DS(G)) = {xwe, ywo} U {wiui, wiv; for 1 <7 < n} and 
| E(DS(G)) |= 6n + 3. 

The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,6n + 3} is as follows: 


f(x) = 0; f(y) = 4n + 2; f(wi) = 2n + 2; f(we) = 4n + 3; f(ui) = 5n+4—i and f(ui) = 
6n+4—-iforl<i<n. 


The corresponding edge labels are as follows: 


The edge label of w,u; is 4n + 2-7 for 1 <i < n;w vy; is dn- 1-1 for 1 <2 < nj 2we 
is 4n+ 3; zy is 4n + 2 and ywe is 2n. Hence the induced edge labels of G are 6n + 3 distinct 
integers. The DS(n(K4 — e)IT) is graceful. 














Theorem 3.8 The DS(n(K4— 2e)II(a)) is graceful. 


Proof Let G = n(K4 — 2e)II(a) be a graph. Let V(G) = {z,y,ui,u,: 1 < i < n} and 
V(DS(G)) \ V(G) = {wi, wo}. Let E(DS(G)) = {ui cy, yui, cu; viW1, Uwe 21 <i<n} and 
| E(DS(G)) |= 5n+1. 


100 P.Selvaraju, P.Balaganesan, J.Renuka and V.Balaj 


The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,5+ 1} is as follows: 

f(x) = 0; f(y) = 2n+1; f(wi) = 1; f(w2) = n4+1; f(vi) = 5n4+3-2i and f(u;) = 38n+2-1 
forl<i<n. 

The corresponding edge labels are as follows: 

The edge label of xu; is 3n—71+2 for 1 <i < nj ry is 2n+1; yu; isn—i+1 for l1<i< nj; xv; 
is 5n+3-— 22 for 1 <i <n; u;w, is 5n4+ 2-27 for 1 <i <nand ujwe is 2n—714+1 for 1 <i<n. 


Hence the induced edge labels of G are 5n + 1 distinct integers. The DS(n(K4 — 2e)II(a))) is 
graceful. 














Theorem 3.9 The DS(C30K, n) is graceful for n > 3. 


Proof Let graph G = C30Kin be a graph. Let V(K1,,) = {z} U{uj:1<7i<n} and Cs 
be the cycle xyzx. Let V(DS(G))\V(G) = {w1, we}. Let E(DS(G)) = {awe, ywo, ry, yz, zx}U 
{witi, zu; :1<i<njsand | E(DS(G)) | = 2n+5. 

The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,2+ 5} is as follows: 


f(w:) = 15 f(we) = 2 fle) = 4; fly) =5; f(z) = 0 and f(ui) =28+5 for 1<i <n. 
The corresponding edge labels are as follows: 


The edge label of xy is 1; xwe is 2; yw is 3; x22 is 4; yz is 5; zu; is 21+ 5 for 1 <i<nand 
wu; is 2i+4 for 1 <2i<n. Hence the induced edge labels of G are 2n + 5 distinct integers. 
Hence the DS(G) is graceful for n > 3. 














Theorem 3.10 The DS(C30K,.n) is felicitous when n > 3. 


Proof Let G = C30 Kin be a graph. Let V(Ki») = {z} U{u;: 1 <i <n} and C3 be 
the cycle xyzx. Let V(DS(G)) \ V(G) = {wi, wo}. Let E(DS(G)) = {rwe, ywo, ry, yz, zz} U 
{witi, zu; :1<i <n} and | E(DS(G)) |= 2n+5. 

The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,2+.5} is as follows: 

f(wi) =n; f(w2) = 2n + 2; f(x) = 2n4+ 3; f(y) = 2n4+ 4; f(z) = 2n+5 and f(u;) =i-1 
forl<i<n. 

The corresponding edge labels are as follows: 

The labels of the edges xy is (4n + 7)(mod 2n + 5); xw2 is (4n+5)(mod 2n+ 5); ywe is 
(4n + 6)(mod 2n +5); az is (4n+ 8)(mod 2n+ 5); yz is (4n+9)(mod 2n +5); zu; is 7 — 1 for 


1<i<nand wy u; isn+i-—1 for 1<7i<n. Hence the induced edge labels of G are 2n + 5 
distinct integers. Hence the DS(C3OK,,») is a felicitous for n > 3. 














Theorem 3.11 The DS(C30K in is elegant for n> 3. 


Proof Let G = C30 Kin be a graph. Let V(Ki.,) = {z}U{u;: 1 <i <n} and C3 be 
the cycle xyzx and V(DS(G)) \ V(G) = {wi, we}. Let E(DS(G)) = {xwe, ywe, ry, yz, zz} U 


Degree Splitting Graph on Graceful, Felicitous and Elegant Labeling 101 


{witi, zu; :1<i <n} and | E(DS(G) |= 2n+5. 
The required vertex labeling f : V(DS(G)) > {0,1,2,--- , 2+ 5} is as follows: 


f(w1) = n+ 2; f(we) = 2n4+ 4; f(x) =n+3; f(y) = 0; f(z) = 2n+5 and f(u;) =i +1; for 
1l<i<n. 


The corresponding edge labels are as follows: 


The edge labels of ry is (n+ 3); ewe is (8n + 7)(mod 2n + 6); ywe is (2n + 4)(mod 2n + 6); 
xz is (3n + 8)(mod 2n + 6); yz is (2n + 5)(mod 2n + 6); zu; is (2n + 6 + 4)(mod 2n + 6) for 
1L<i<n; wiu; is (n+3+%)(mod2n+6) for1<i<n. Hence the induced edge labels of G 
are 2n + 5 distinct integers. Hence the DS(G) is elegant for n > 3. 














Theorem 3.12 The DS(K2,,) is felicitous for n> 3. 


Proof Let G = (K2,,) be a graph. Let V(G) = {v1, va} U{uj: 1 <i <n} and V(DS(G))\ 
V(G) = {wi, we}. Let E(DS(G)) = {wov1, wove} U {wiu; : 1 <i < n} and | E(DS(G)) |= 
3n + 2. 


The required vertex labeling f : V(DS(G)) > {0,1,2,--+ ,3m+ 2} is as follows: 
f(ui) = 3n+ 5 — 3% for 1 <i <n; f(vi) = 0; f(v2) = 8n + 1; f(wi) = 1 and f(we) = 3. 
The corresponding edge labels are as follows: 


The edge label of wyu; is (8n + 6 — 32)(mod 3n 4+ 2) forl < i < niujvi is (Bn +5 —-— 
3i)(mod 3n + 2) for 1 <i < n; uve is (6n + 6 — 3t)(mod 3n + 2) for 1 <i < nj; wevy is 3 and 
wev2 is 3n + 4(mod 3n + 2). Hence the induced edge labels of G are 3n + 2 distinct integers. 
Hence DS(K2,,) is felicitous for n > 3. 














Theorem 3.13 The DS(K2,,) is elegant for n > 3. 


Proof Let G = (K2,,) be a graph, LetV(G) = {v1, vo} U {uj : 1 <i < nm} and V(DS(G)) \ 
V(G) = {wi, we}. Let E(DS(G)) = {wov1, wove} U {wiu; : 1 <i < n} and | E(DS(G)) |= 
3n + 2. 


The required vertex labeling f : V(DS(G)) > {0,1,2,--- ,3n+ 2} is as follows: 
f(ui) = 38n+5— 3% for 1 <i<n;f(v1) = 0; f(ve) = 3n +1; f(w1) = 2 and f(we) = 4. 
The corresponding edge labels are as follows: 


The edge label of w iu; is (8n + 7 — 3i)(mod 3n + 3) for 1 < i < njujy is (8n +5 — 
31)(mod 3n + 3) for 1 <i <n; ujve is (6n + 6 — 32)(mod 3n 4+ 3) for 1 <i <n; wevy is 4 and 
wev2 is 3n +5 (mod 3n +3) . Hence the induced edge labels of G are 3n + 2 distinct integers 
.The DS(G) is elegant for n > 3. 














102 P.Selvaraju, P.Balaganesan, J.Renuka and V.Balaj 


References 


[1] J.A.Gallian, A dynamic survey of graph labeling, The Electronic. J. Combinatorics, 16(2009), 
##DS6. 

[2] E.Sampathkumar and Walikar, On the splitting graph of a graph, The Karnataka Univer- 
sity Journal Science, 25(1980), 13-16. 

[3] Sethuraman G. and Selvaraju.P, New classes of graphs on graph labeling, National Con- 
ference on Discrete Mathematics and the Applications, Thirunelveli, January 5-7, 2000. 


Math. Combin. Book Ser. Vol.2(2012), 103-109 


Distance Two Labeling of Generalized Cacti 


S.K.Vaidya 


(Saurashtra University, Rajkot - 360005, Gujarat, India) 


D.D.Bantva 


(L.E. College, Morvi - 363642, Gujarat, India) 
E-mail: samirkvaidya@yahoo.co.in, devsi.bantva@gmail.com 


Abstract: A distance two labeling of a graph G is a function f from the vertex set V(G) to 
the set of all nonnegative integers such that | f(x)—f(y)| > 2 if d(x, y) = 1 and |f(x)—f(y)| => 
1 if d(w,y) = 2. The L(2,1)-labeling number A(G) of G is the smallest number k such that 
G has an L(2, 1)-labeling with max{f(v) : v € V(G)} =k. Here we introduce a new graph 


family called generalized cactus and investigate the A-number for the same. 
Key Words: Channel assignment, interference, distance two labeling, block, cactus. 


AMS(2010): 05C78 


§1. Introduction 


In a communication network, the main task is to assign a channel (non negative integer) to 
each TV or radio transmitters located at different places such that communication do not 
interfere. This problem is known as channel assignment problem which was introduced by Hale 
[4]. Usually, the interference between two transmitters is closely related with the geographic 
location of the transmitters. If we consider two level interference namely major and minor 
then two transmitters are very close if the interference is major while close if the interference 
is minor. Robert [7] proposed a variation of the channel assignment problem in which close 
transmitters must receive different channels and very close transmitters must receive channels 
that are at two apart. 

In a graph model of this problem, the transmitters are represented by the vertices of a 
graph; two vertices are very close if they are adjacent and close if they are at distance two 
apart in the graph. Motivated through this problem Griggs and Yeh [3] introduced L(2,1)- 
labeling which is defined as follows: 


Definition 1.1 A distance two labeling (or L(2,1)-labeling) of a graph G = (V(G), E(G)) is a 
function f from vertex set V(G) to the set of all nonnegative integers such that the following 


conditions are satisfied: 


1Received March 14, 2012. Accepted June 25, 2012. 


104 S.K. Vaidya and D.D.Bantva 


(1) |f(x) — f(y)| = 2 if d(a,y) = 1; 
(2) |f(z) —f(y)| = 1 if d(a,y) = 2. 


The span of f is defined as max{| f(u) — f(v) |: u,v € V(G)}. The A-number for a graph 
G, denoted by A(G) which is the minimum span of a distance two labeling for G. The L(2, 1)- 
labeling is studied in the past two decades by many researchers like Yeh [14]-[15], Georges and 
Mauro [2], Sakai [8], Chang and Kuo [1], Kuo and Yan [5], Lu et al. [6], Shao and Yeh [9], 
Wang [12], Vaidya et al. [10] and by Vaidya and Bantva [11]. 

We begin with finite, connected and undirected graph G = (V(G), E(G)) without loops 
and multiple edges. For the graph G, A denotes the maximum degree of the graph and N(v) 
denotes the neighborhood of v. Also in the discussion of distance two labeling [0, k] denotes 
the set of integers {0,1,--- ,&}. For all other standard terminology and notations we refer to 
West [13]. Now we will state some existing results for ready reference. 


Proposition 1.2({1]) ACUH) < A(G), for any subgraph H of a graph G. 
Proposition 1.3({14]) The A-number of a star Kya is A+1, where A is the maximum degree. 


Proposition 1.4((1]) If \(G) = A+1 then f(v) =0 or A+1 for any (G)-L(2, 1)-labeling 
f and any vertex v of maximum degree A. In this case, N{v] contains at most two vertices of 
degree A, for any vertex v € V(G). 


§2. Main Results 


The problem of labeling of trees with a condition at distance two remained the focus of many 
research papers as its A-number depends upon the maximum degree of a vertex. In [3], Griggs 
and Yeh proved that the \-number of any tree T with maximum degree A is either A+1 or A+2. 
They obtained the A-number by first-fit greedy algorithm. Later, trees are classified according 
to their \-numbers. The trees with A-number A + 1 are classified as class one otherwise they 
are of class two. Earlier it was conjectured that the classification problem is NP-complete but 
Chang and Kuo [1] presented a polynomial time classification algorithm. But even today the 
classification of trees of class two is an open problem. Motivated through this problem, we 
present here a graph family which is not a tree but its A-number is either A+ 1 or A+ 2 and 
it is a super graph of tree. 

A block of a graph G is a maximal connected subgraph of G that has no cut-vertex. An 
n-complete cactus is a simple graph whose all the blocks are isomorphic to K,,. We denote it 
by C(K,,). An n-complete k-regular cactus is an n-complete cactus in which each cut vertex is 
exactly in k blocks. We denote it by C(K,,(k)). The block which contains only one cut vertex 
is called leaf block and that cut vertex is known as leaf block cut vertex. We illustrate the 
definition by means of following example. 


Example 2.1 A 3-complete cactus C(K3) and 3-complete 3-regular cactus are shown in Fig.1 
and Fig.2 respectively. 


Distance Two Labeling of Generalized Cacti 105 


Fig.1 


Fig.2 


Theorem 2.2 Let C(Kn(k)) be an n-complete k-regular cactus with maximum degree A and 
k > 3. Then (C(K,(k))) ts either A+1 or A+2. 


Proof Let C(K,(k)) be an n-complete k-regular cactus with maximum degree A. The star 
Kya is a subgraph of C(K,,(k)) and hence A\(C(K,,(k))) > A+1. 
For upper bound, we apply the following Algorithm: 


Algorithm 2.3 The L(2,1)-labeling of given n-complete k-regular cactus. 


Input An n-complete k-regular cactus graph with maximum degree A. 


Idea Identify the vertices which are at distance one and two apart. 
Initialization Let vp be the vertex of degree A. Label the vertex vp by 0 and take S = 


{vo}- 


106 S.K. Vaidya and D.D.Bantva 


Iteration Define f : V(G) — {0,1,2,...} as follows. 


Step 1 Find N(wvo). If N(vo) = {v1, ve ,..., va} then partition N(vo) into k sets Vi, Va, ... 
Ve such that for each i = 1,2,...,4 the graph induced by V; U {vo} forms a complete subgraph 
of C(K,,(k)). The definition of C(K,,(k)) itself confirms the existence of such partition with 
the characteristic that for i A 7, ue Vi, v € Vj, d(u,v) = 2. 

Step 2 Choose a vertex v; € N(vo) and define f(v1) = 2. Find a vertex v2 € N(vo) such 
that d(v1, v2) = 2 and define f(v2) = 3. Continue this process until all the vertices of N(vo) 
are labeled. Take S = {uo} U {uv € V(G)/f(v) is a label of v}. 

Step 3 For f(v;) = 7%. Find N(v;) and define f(v) = the smallest number from the set 
{0,1,2,---} — {i—1,7,7+ 1}, where v € N(v;) — S such that |f(u) — f(v)| > 2 if d(u,v) = 1 
and |f(u) — f(v)| > 1 if d(u,v) =2. Denote S U {v € V(G)/f(v) is a label of v} = S?. 

Step 4 Continue this recursive process till S” = V(G), where S" = S"~1 U{v € V(G)/f(v) 
is a label of v}. 

Output max{f(v)/v €E V(G)} =A+42. 


Hence, A(C(Kn(k))) < A+2.Thus, (C(K,,(k))) is either A+1 or A+ 2. 














Example 2.4 In Fig.3, the £(2,1)-labeling of 3-complete 3-regular cactus C'(¢3(3)) is shown 
for which \(C(K3(3))) = A+2 = 8. 





Griggs and Yeh [3] have proved that: 


(1) A(P2) = 2; 

(2) A(P3) = A(P1) = 3, and (3) A(P,,) = 4, for n > 5. This can be verified by Proposition 
1.4 and using our Algorithm 2.3. In fact, any path P, is 2-complete 2-regular cactus C'(K2(2)). 
Thus a single Algorithm will work to determine the \-number of path P,,. Using Algorithm 2.3 
the L(2,1)-labeling of P2, P3, Py and Ps is demonstrated in Fig.4. 


Distance Two Labeling of Generalized Cacti 107 








: a : : 
P» P4 
poo 8 2 oo 8 
P3 Ps 
Fig.4 


Theorem 2.5 Let C(K,,) be an n-complete cactus with at least one cut verter which belongs 
to at least three blocks. Then \(C(Ky)) is either A+1 or A+2. 


Proof Let C(K,,) be the arbitrary an n-complete cactus with maximum degree A. The 
graph K1,q is a subgraph of C(K,,) and hence by Propositions 1.2 and 1.3 \(C(K,)) > A+1. 
Moreover C(K,,) is a subgraph of C(K,,(k)) (where k is -4,) and hence by Proposition 1.2 and 


n 


Theorem 2.2, \(C(K,)) < A+ 2. Thus, we proved that A(C(K,)) is either A+1 or A+2. 














Now as a corollary of above result it is easy to show that the A-number of any tree with 
maximum degree A is either A +1 or A+ 2. We also present some other graph families as a 
particular case of above graph families whose A-number is either A+ 1 or A+ 2. 


Corollary 2.6 Let T be a tree with maximum degree A > 2. Then X(T) is either A+ 1 or 
A +2. 


Proof Let T be a tree with maximum degree A > 2. If A = 2 then T is a path and 
problem is settled. But if A > 2 then A(T) > A+1 as Kj, is a subgraph of T. The upper 
bound of A-number is A + 2 according to Theorem 2.5 as any tree T' is a 2-complete cactus 
C(K2). Thus, we proved that X(T) is either A+1 or A +2. 














Example 2.7 In Fig.5, the L(2, 1)-labeling of tree T is shown which is 2-complete cactus C'(K2) 
with maximum degree A = 3 for which X(T) = A(C(K2)) = A+2 =5. 





Fig.5 


108 S.K. Vaidya and D.D.Bantva 


Corollary 2.8 (Kin) =n+1. 


Proof The star Ky, is a 2-complete n-regular cactus. Then by Theorem 2.2, \(Ain) = 
n+1. 














Corollary 2.9 For the Friendship graph F,,, (Fn) = 2n+1. 


Proof The Friendship graph F;, is a 3-complete 2n-regular cactus. Then by Theorem 2.2, 
AM Fr) = 2n+1. 














Example 2.10 In Fig.6 and Fig.7, the L(2,1)-labeling of star Ky,4 and Friendship graph Fy 
are shown for which A-number is 5 and 9 respectively. 


3 2 


Fig.6 





Fig.7 


§3. Concluding Remarks 


We have achieved the A-number of an n-complete k-regular cactus. The A-numbers of some 
standard graphs determined earlier by Griggs and Yeh [3] can be obtained as particular cases 


of our results which is the salient feature of our investigations. 


Distance Two Labeling of Generalized Cacti 109 


References 


1 





10 


11 


12 


13 
14 





15 





G.J.Chang and D.Kuo, The L(2,1)-labeling problem on graphs, SIAM J. Discrete Math., 
9(2)(1996), 309-316. 

J.P.Georges and D.W.Mauro, Labeling trees with a condition at distsnce two, Discrete 
Math., 269(2003), 127-148. 

J.R.Griggs and R.K.Yeh, Labeling graphs with condition at distance 2, SIAM J. Discrete 
Math., 5(4)(1992), 586-591. 

W.K.Hale, Frequency assignment:Theory and applications, Proc. IEEE, 68(12)(1980), 
1497-1514. 

D.Kuo and J.Yan, On L(2,1)-labelings of cartesian products of paths and cycles, Discrete 
Math., 283(2004), 137-144. 

C.Lu, L.Chen, M.Zhai, Extremal problems on consecutive L(2, 1)-labeling, Discrete Applied 
Math., 155(2007), 1302-1313. 

F.S.Robert, T-coloring of graphs: recent results and open problems, Discrete Math., 93(1991), 
229-245. 

D.Sakai, Labeling chordal graphs: distance two condition, SIAM J. Discrete Math., 7(1)(1994), 
133-140. 

Z.Shao and R.Yeh, The L(2,1)-labeling and operations of graphs, IEEE Transactions on 
Circuits and Systems-I, 52(3)(2005), 668-671. 

S.K.Vaidya, P.L.Vihol, N.A.Dani and D.D.Bantva, L(2,1)-labeling in the context of some 
graph operations, Journal of Mathematics Research, 2(3)(2010), 109-119. 

S.K.Vaidya and D.D.Bantva, Labeling cacti with a condition at distance two, Le Matem- 
atiche, 66(2011), 29-36. 

W.Wang, The L(2,1)-labeling of trees, Discrete Applied Math., 154(2006), 598-603. 
D.B.West, Introduction to Graph theory, Printice -Hall of India, 2001. 

R.K.Yeh, Labeling Graphs with a Condition at Distance Two, Ph.D.Thesis, Dept.of Math., 
University of South Carolina, Columbia,SC, 1990. 

R.K.Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math., 
306(2006), 1217-1231. 


As far as the laws of mathematics refer to reality, they are not certain; and 
as far as they are certain, they do not refer to reality. 


By Albert Einstein, an American theoretical physicist.. 


Author Information 


Submission: Papers only in electronic form are considered for possible publication. Papers 
prepared in formats, viz., .tex, .dvi, .pdf, or.ps may be submitted electronically to one member 
of the Editorial Board for consideration in the Mathematical Combinatorics (Interna- 
tional Book Series (ISBN 978-1-59973-186-5). An effort is made to publish a paper duly 
recommended by a referee within a period of 3 months. Articles received are immediately put 
the referees/members of the Editorial Board for their opinion who generally pass on the same 
in six week’s time or less. In case of clear recommendation for publication, the paper is accom- 
modated in an issue to appear next. Each submitted paper is not returned, hence we advise 


the authors to keep a copy of their submitted papers for further processing. 


Abstract: Authors are requested to provide an abstract of not more than 250 words, lat- 
est Mathematics Subject Classification of the American Mathematical Society, Keywords and 
phrases. Statements of Lemmas, Propositions and Theorems should be set in italics and ref- 
erences should be arranged in alphabetical order by the surname of the first author in the 
following style: 


Books 


4\Linfan Mao, Combinatorial Geometry with Applications to Field Theory, InfoQuest Press, 
2009. 
12]W.S.Massey, Algebraic topology: an introduction, Springer-Verlag, New York 1977. 


Research papers 


6|Linfan Mao, Combinatorial speculation and combinatorial conjecture for mathematics, In- 
ternational J.Math. Combin., Vol.1, 1-19(2007). 
9|Kavita Srivastava, On singular H-closed extensions, Proc. Amer. Math. Soc. (to appear). 





Figures: Figures should be drawn by TEXCAD in text directly, or as EPS file. In addition, 
all figures and tables should be numbered and the appropriate space reserved in the text, with 
the insertion point clearly indicated. 


Copyright: It is assumed that the submitted manuscript has not been published and will not 
be simultaneously submitted or published elsewhere. By submitting a manuscript, the authors 
agree that the copyright for their articles is transferred to the publisher, if and when, the 
paper is accepted for publication. The publisher cannot take the responsibility of any loss of 
manuscript. Therefore, authors are requested to maintain a copy at their end. 


Proofs: One set of galley proofs of a paper will be sent to the author submitting the paper, 
unless requested otherwise, without the original manuscript, for corrections after the paper is 
accepted for publication on the basis of the recommendation of referees. Corrections should be 
restricted to typesetting errors. Authors are advised to check their proofs very carefully before 


return. 


Mathematical Combinatorics (International Book Series) June, 2012 


alg 
9 


Contents 


Neutrosophic Rings IT 
BY AGBOOLA A.A.A., ADELEKE E.O. and AKINLEYE S.A 


Non-Solvable Spaces of Linear Equation Systems 

BY LINFAN MAO 

Roman Domination in Complementary Prism Graphs 

BY B.CHALUVARAJU AND V.CHAITRA 

Enumeration of Rooted Nearly 2-Regualr Simple Planar Maps 

BY SHUDE LONG AND JUNLIANG CAI 

On Pathos Total Semitotal and Entire Total Block Graph of a Tree 
BY MUDDEBIHAL M. H. AND SYED BABAJAN 

On Folding of Groups BY MOHAMED ESMAIL BASHER....................52 
On Set-Semigraceful Graphs 

BY ULLAS THOMAS AND SUNIL C. MATHEW 

On Generalized m-Power Matrices and Transformations 

BY SUHUA YE, YIZHI CHEN AND HUI LUO 

Perfect Domination Excellent Trees BY SHARADA B 

On (k,d)-Maximum Indexable Graphs and (k,d)-Maximum 
Arithmetic Graphs BY ZEYNAB KHOSHBAKHT 

Total Dominator Colorings in Paths BY A.VIJAYALEKSHMI 

Degree Splitting Graph on Graceful, Felicitous and Elegant Labeling 
BY P.SELVARAJU, P.BALAGANESAN, J-.RENUKA AND V.BALAJ 
Distance Two Labeling of Generalized Cacti 


BY S.K.VAIDYA AND D.D.BANTVA 





SEN SO VeI9S (30865 


TedessMeM Ties ALGKe\)