On Mutually Orthogonal Graph-Path Squares

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.

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/