The (A,D) - Ascending Subgraph Decomposition of Cartesian Product of
some Simple Graphs

S. Asha

doi:https://doi.org/10.14445/22315373/IJMTT-V21P507

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 21 | Number 1 | Year 2015 | Article Id. IJMTT-V21P507 | DOI : https://doi.org/10.14445/22315373/IJMTT-V21P507

The (A,D) - Ascending Subgraph Decomposition of Cartesian Product of some Simple Graphs

S. Asha

Abstract

Alavi et al[1] defined Ascending Subgraph Decomposition(ASD) as decomposition of G with size n + 1 2       into n subgraphs G1,G2,G3, . . . ,Gn without isolated vertices such that each Gi is isomorphic to a proper subgraph of Gi+1 for 1 i  n–1 and |E(Gi )| = i for 1 i  n. Let G be a graph of size n 2 (2a + (n – 1)d) where a, n, d are positive integers. Then G is said to have (a,d) - Ascending Subgraph Decomposition ((a,d) -ASD) into n parts if the edge set of G can be partitioned into n non-empty sets generating subgraphs G1,G2, . . .,Gn without isolated vertices such that each Gi is isomorphic to a proper subgraph of Gi+1 for 1 i  n–1 and |E(Gi)| = a + (i–1)d for 1  i  n. The cartesian product G1 x G2 of two graphs G1 and G2 is defined to be the graph whose vertex set is V1 x V2 and two vertices u = (u1,u2) and v = (v1,v2) in V = V1 x V2 are adjacent in G1 x G2 if either u1 = v1 and u2 is adjacent to v2 or u2 = v2 and u1 is adjacent to v1. In this paper, I investigate the (a,d) - Ascending Subgraph Decomposition of Pn+1 x K2.

Keywords

Ascending Subgraph Decomposition , cartesian product.

References

[1] Y. Alavi, A.J. Boals, G. Chartrand, P. Erdos and O.R. Oellerman, The ascending subgraph decomposition problem, Congressus Numerantium, 58 (1987), 7-14.
[2] S. Asha, R. Kala, Continuous Monotonic Decomposition of Tensor Product of Some Simple Graphs, Asian Journal of Current Engineering and Maths, 4 Jul-Aug(2012), 177-184.
[3] F. Harary, Graph Theory, Addition - Wesley Publishing Company Inc, USA, 1969, pp 286.
[4] Huang-Lin Fu, A note on the Ascending Subgraph Decomposition, Discrete Mathematics, 84(1990), 315-318.
[5] A. Nagarajan and S. Navaneethakrishnan, The (a,d) - Ascending subgraph Decomposition, Tamkang Journal of Mathematics, Vol. 37 (2006), No. 4.
[6] A. Nagarajan and S. Navaneethakrishnan, The (a,d) - Ascending subgraph Decomposition of K1,m x K2, Acta Ciencia Indica, Vol XXXII M, No.3 (2006), 1341- 1356.
[7] S.G. Telang, Number Theory, Tata Mcgraw-Hill Publishing Company, pp 660.

Citation :

S. Asha, "The (A,D) - Ascending Subgraph Decomposition of Cartesian Product of some Simple Graphs," International Journal of Mathematics Trends and Technology (IJMTT), vol. 21, no. 1, pp. 52-57, 2015. Crossref, https://doi.org/10.14445/22315373/IJMTT-V21P507