On Mutually Orthogonal Graph-Path Squares
Author(s)
Ramadan El-Shanawany*
Affiliation(s)
Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf, Egypt.
Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf, Egypt.
ABSTRACT
A decomposition 
of a graph H is a partition of the edge set of H into edge-disjoint subgraphs 
. If 
for all 
, then G is a decomposition of H by G.
Two decompositions 
and 
of the complete
bipartite graph 
are orthogonal if, 
for all 
. A set of decompositions 
of 
is a set of k mutually orthogonal graph squares (MOGS) if 
and 
are orthogonal for all 
and 
. For any bipartite graph G with n edges, 
denotes the maximum number k in a largest possible set 
of MOGS of 
by G. Our objective in this
paper is to compute 
where 
is a path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an
isomorphic to a certain graph F).
Cite this paper
El-Shanawany, R. (2016) On Mutually Orthogonal Graph-Path Squares. Open Journal of Discrete Mathematics, 6, 7-12. doi: 10.4236/ojdm.2016.61002.
El-Shanawany, R. (2016) On Mutually Orthogonal Graph-Path Squares. Open Journal of Discrete Mathematics, 6, 7-12. doi: 10.4236/ojdm.2016.61002.
References
[1] Balakrishnan, R. and Ranganathan, K. (2012) A Textbook of Graph Theory. Springer, Berlin.
http://dx.doi.org/10.1007/978-1-4614-4529-6 [2] Alspach, B., Heinrich, K. and Liu, G. (1992) Orthogonal Factorizations of Graphs. In: Dinitz, J.H. and Stinson, D.R., Eds., Contemporary Design Theory, Chapter 2, Wiley, New York, 13-40. [3] Gronau, H.-D.O.F., Hartmann, S., Grüttmüller, M., Leck, U. and Leck, V. (2002) On Orthogonal Double Covers of Graphs. Designs, Codes and Cryptography, 27, 49-91.
http://dx.doi.org/10.1023/A:1016546402248 [4] Colbourn, C.J. and Dinitz, J.H. (eds.) (2007) Handbook of Combinatorial Designs. 2nd Edition, Chapman & Hall/CRC, London, Boca Raton. [5] Colbourn, C.J. and Dinitz, J.H. (2001) Mutually Orthogonal Latin Squares: A Brief Survey of Constructions. Journal of Statistical Planning and Inference, 95, 9-48.
http://dx.doi.org/10.1016/S0378-3758(00)00276-7 [6] El-Shanawany, R. (2002) Orthogonal Double Covers of Complete Bipartite Graphs. Ph.D. Thesis, Universitat Rostock, Rostock. [7] Sampathkumar, R. and Srinivasan, S. (2009) Mutually Orthogonal Graph Squares. Journal of Combinatorial Designs, 17, 369-373.
http://dx.doi.org/10.1002/jcd.20216 [8] El-Shanawany, R., Gronau, H.-D.O.F. and Grüttmüller, M. (2004) Orthogonal Double Covers of Kn,n by Small Graphs. Discrete Applied Mathematics, 138, 47-63.
http://dx.doi.org/10.1016/S0166-218X(03)00269-5 [9] El-Shanawany, R., Shabana, H. and ElMesady, A. (2014) On Orthogonal Double Covers of Graphs by Graph-Path and Graph-Cycle. LAP LAMBERT Academic Publishing.
https://www.lappublishing.com/
[1] Balakrishnan, R. and Ranganathan, K. (2012) A Textbook of Graph Theory. Springer, Berlin.
http://dx.doi.org/10.1007/978-1-4614-4529-6 [2] Alspach, B., Heinrich, K. and Liu, G. (1992) Orthogonal Factorizations of Graphs. In: Dinitz, J.H. and Stinson, D.R., Eds., Contemporary Design Theory, Chapter 2, Wiley, New York, 13-40. [3] Gronau, H.-D.O.F., Hartmann, S., Grüttmüller, M., Leck, U. and Leck, V. (2002) On Orthogonal Double Covers of Graphs. Designs, Codes and Cryptography, 27, 49-91.
http://dx.doi.org/10.1023/A:1016546402248 [4] Colbourn, C.J. and Dinitz, J.H. (eds.) (2007) Handbook of Combinatorial Designs. 2nd Edition, Chapman & Hall/CRC, London, Boca Raton. [5] Colbourn, C.J. and Dinitz, J.H. (2001) Mutually Orthogonal Latin Squares: A Brief Survey of Constructions. Journal of Statistical Planning and Inference, 95, 9-48.
http://dx.doi.org/10.1016/S0378-3758(00)00276-7 [6] El-Shanawany, R. (2002) Orthogonal Double Covers of Complete Bipartite Graphs. Ph.D. Thesis, Universitat Rostock, Rostock. [7] Sampathkumar, R. and Srinivasan, S. (2009) Mutually Orthogonal Graph Squares. Journal of Combinatorial Designs, 17, 369-373.
http://dx.doi.org/10.1002/jcd.20216 [8] El-Shanawany, R., Gronau, H.-D.O.F. and Grüttmüller, M. (2004) Orthogonal Double Covers of Kn,n by Small Graphs. Discrete Applied Mathematics, 138, 47-63.
http://dx.doi.org/10.1016/S0166-218X(03)00269-5 [9] El-Shanawany, R., Shabana, H. and ElMesady, A. (2014) On Orthogonal Double Covers of Graphs by Graph-Path and Graph-Cycle. LAP LAMBERT Academic Publishing.
https://www.lappublishing.com/