Mutually orthogonal graph squares

✍ Scribed by R. Sampathkumar; S. Srinivasan

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 89 KB
• Volume: 17
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20216

✦ Synopsis

Abstract

A decomposition 𝒢={G~1~, G~2~,…,G~s~} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G~1~, G~2~,…,G~s~. If G~i~≅H for all i∈{1, 2, …, s}, then 𝒢 is a decomposition of G by H. Two decompositions 𝒢={G~1~, G~2~, …, G~n~} and ℱ={F~1~, F~2~,…,F~n~} of the complete bipartite graph K~n,n~ are orthogonal if |E(G~i~)∩E(F~j~)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {𝒢~1~, 𝒢~2~, …, 𝒢~k~} of K~n, n~ is a set of k mutually orthogonal graph squares (MOGS) if 𝒢~i~ and 𝒢~j~ are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {𝒢~1~, 𝒢~2~, …, 𝒢~k~} of MOGS of K~n, n~ by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P~p+ 1~)=p, where P~p+ 1~ is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009