Enumeration of Glued Graphs of Paths

Monthiya Ruangnai, Sayan Panma


Let \(G_1\) and \(G_2\) be two vertex-disjoint graphs with \(H_1\) a subgraph of \(G_1\) and \(H_2\) a subgraph of \(G_2\). Let \(f:H_1 \rightarrow H_2\) be an isomorphism between these subgraphs. The glued graph of \(G_1\) and \(G_2\) at \(H_1\) and \(H_2\) with respect to \(f\) is the graph that results from combining \(G_1 \cup G_2\) by identifying the subgraphs \(H_1\) and \(H_2\) according to the isomorphism \(f\) between \(H_1\) and \(H_2\). We refer \(G_1\) and \(G_2\) as its original graphs and refer \(H\) as its clone where \(H\) is a copy of \(H_1\) and \(H_2\). In this paper, we enumerate all non-isomorphic resulting glued graphs between two paths at connected clones. Moreover, we also give the characterization of the glued graph at a connected clone.


A glued graph; The glue operator; Glued graph of paths; Graphs enumeration; Graph isomorphisms

Full Text:



V. Boonthong, P. Putthapiban, P. Chaisuriya and P. Pacheenburawana, Eulerian glued graphs, Thai J. Math. 8(1) (2010), 103 – 109, URL http://thaijmath.in.cmu.ac.th/index.php/thaijmath/article/view/307.

J. L. Gross and J. Yellen, Graph Theory and Its Applications, 2nd ed., Chapman & Hall, United States of America (2006), URL http://cds.cern.ch/record/902845.

S. Malila, The Upper and Lower Independence Numbers of Glued Graphs of Cycles, Master Thesis, Mahidol University, Thailand (2014), URL: https://graduate.mahidol.ac.th/engine/currentstudents/detail/abstract_view.php?id=5436612.

J. Mekwian, Glued Graphs for Solving E-logistics Network Problems, Master Thesis, King Mongkut’s Institute of Technology Ladkrabang, Thailand (2007), URL: http://newtdc.thailis.or.th/docview.aspx?tdcid=330282.

W. Pimpasalee and C. Uiyyasathian, Clique coverings of glued graphs at complete clone, Int. Math. Forum 5(24) (2010), 1155 – 1166, URL: https://pdfs.semanticscholar.org/e9a7/9935e33fda38cc4b168594f6f7e1f90a2d09.pdf.

C. Promsakon, Colorability of Glued Graphs, master thesis, Chulalongkorn University, Thailand (2006), URL https://cuir.car.chula.ac.th/handle/123456789/15010.

S. M. Seyyedi and F. Rahmati, Some properties of glued graphs at complete clone in the view of algebraic combinatorics, Sci. Int. (Lahore) 27(1) (2014), 39 – 47, URL: http://www.sci-int.com/pdf/112019674939-47%20-Seyyede%20Masoome%20Seyyedi%20%20COMPOSED%20MATH.--IRAN-GP.pdf.

C. Uiyyasathian, Maximal-Clique Partitions, Doctoral Thesis, University of Colorado at Denver, USA (2003), 39 – 42, URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=

C. Uiyyasathian and U. Jongthawonwuth, Clique partitions of glued graphs, J. Math. Research 2(2) (2010), 104 – 111, DOI: 10.5539/jmr.v2n2p104.

C. Uiyyasathian and S. Saduakdee, Perfect glued graph at complete clones, J. Math. Research 1(1) (2009), 25 – 30, DOI: 10.5539/jmr.v1n1p25.

R. Wilson and J. J. Watkins, Graphs: An Introductory Approach A First course in Discrete Mathematics, John Wiley & Sons, United States of America (1990), URL: https://www.wiley.com/enus/Graphs%3A+An+Introductory+Approach+A+First+Course+in+Discrete+Mathematics-p-9780471615545.

R. Wilson, Introduction to Graph Theory, 4th edition, Addison Wesley Longman Limited, England (1996), URL: https://pdfslide.net/documents/robin-j-wilson-introduction-tograph-theory-4th-edition.html.

DOI: http://dx.doi.org/10.26713%2Fcma.v10i4.1252


  • There are currently no refbacks.

eISSN 0975-8607; pISSN 0976-5905