Labeled graph rearrangements on matched and star products

Amir Barghi, Daryl DeFord

Abstract


In this paper we present enumerative results for Stirling numbers of the first kind for two graph products, the matched product and the m-star, using the combinatorial model of rearrangements. The kth Stirling number of the first kind for a simple graph G counts the number of ways to decompose G into exactly k vertex-disjoint cycles, including single vertices as 1-cycles, single edges as 2-cycles, and counting orientations for cycles of order three or higher. This naturally leads to the definition of the graphical factorial of G as the total number of such decompositions without any restrictions on the number of cycles involved. The matched product, motivated by a popular construction for modeling multiplex data, requires specifying a labeling of each component graph and naturally defines several families of graphs whose Stirling numbers of the first kind can be enumerated in terms of their component graphs. The m-star product of a graph G is defined as the join of G with the empty graph with m vertices. We compute the Stirling numbers of the first kind and factorials for the m-star of complete graphs, forests, and cycles, and we provide bounds for other families. The combinatorial proofs in the case of m-star products also motivate a generalization in terms of disjoint path decompositions of graphs, which provides another promising avenue of study.

Keywords


graph Stirling number of the first kind; graph factorial; matched product; cycle cover

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.7

References

D. Fitriani, A. N. M. Salman, and Z. Y. Awanis, “Rainbow connection number of comb product of graphs,” Electronic Journal of Graph Theory and Applications, vol. 10, no. 2, pp. 461–474, 2022.

R. Y. Wulandari and R. Simanjuntak, “Distance antimagic labelings of product graphs,” Electronic Journal of Graph Theory and Applications, vol. 11, no. 1, pp. 111–123, 2022.

K. Somasundaram, T. Geetha, and R. Vignesh, “Total coloring conjecture on certain classes of product graphs,” Electronic Journal of Graph Theory and Applications, vol. 11, no. 1, pp. 223–234, 2023.

D. R. DeFord, “Counting rearrangements on generalized wheel graphs,” Fibonacci Quarterly, vol. 51, no. 3, pp. 259–267, 2013.

D. R. DeFord, “Seating rearrangements on arbitrary graphs,” Involve, vol. 7, no. 6, pp. 787–805, 2014.

I. Tomescu, “Méthodes combinatoires dans le théorie des automates finis,” Ph.D. Thesis, Bucharest, Romania, 1971.

B. Duncan and R. Peele, “Bell and Stirling numbers for graphs,” Journal of Integer Sequences, vol. 12, no. 09.7, p. 1, 2009.

B. Duncan, “Bell numbers of graphs,” Ph.D. Thesis, Auburn University, 2012.

D. Galvin and D. T. Thanh, “Stirling numbers of forests and cycles,” Electronic Journal of Combinatorics, vol. 20, no. 1, P73, 2013.

Z. Kereskényi-Balogh and G. Nyul, “Stirling numbers of the second kind and Bell numbers for graphs,” Australasian Journal of Combinatorics, vol. 58, pp. 264–274, 2014.

J. Allagan and C. Serkan, “Bell numbers of complete multipartite graphs,” Computer Science Journal of Moldova, vol. 71, no. 2, pp. 234–242, 2016.

A. Barghi, “Stirling numbers of the first kind for graphs,” Australasian Journal of Combinatorics, vol. 70, no. 2, pp. 253–268, 2018.

E. J. Farrell, “On a general class of graph polynomials,” Journal of Combinatorial Theory Series B, vol. 26, no. 1, pp. 111–122, 1979.

S. Chiba and T. Yamashita, “Degree conditions for the existence of vertex-disjoint cycles and paths: A survey,” Graphs and Combinatorics, vol. 34, no. 1, pp. 1–83, 2018.

K. J. Gonzales, “Cyclic and linear graph partitions and normal ordering,” Journal of Integer Sequences, vol. 25, 22.1.1, 2022.

J. Engbers, D. Galvin, and J. Hilyard, “Combinatorially interpreting generalized Stirling numbers,” European Journal of Combinatorics, vol. 43, pp. 32–54, 2015.

R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2016.

W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience, New York, 2000.

M. Magnani, B. Micenkova, and L. Rossi, “Combinatorial analysis of multiple networks,” preprint, pp. 1–17, 2013.

H. Sayama, “Graph product multilayer networks: spectral properties and applications,” Journal of Complex Networks, vol. 6, no. 3, pp. 430–447, 2018.

P. Skardal, “Diffusion dynamics and synchronizability of hierarchical products of networks,” Physical Review E, vol. 96, 042302, 2017.

X. Ding and T. Jiang, “Spectral distributions of adjacency and Laplacian matrices of random graphs,” Annals of Applied Probability, vol. 20, no. 6, pp. 2086–2117, 2010.

L. Erdős, A. Knowles, H.-T. Yau, and J. Yin, “Spectral statistics of Erdős–Rényi graphs I: Local semicircle law,” Annals of Applied Probability, vol. 41, no. 3B, 2013.

J. Choi and H. M. Srivastava, “Some summation formulas involving harmonic numbers and generalized harmonic numbers,” Mathematical and Computer Modelling of Dynamical Systems, vol. 54, no. 9-10, pp. 2220–2234, 2011.

R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley Longman Publishing Co., Inc., USA, 1994.

A. T. Benjamin, G. O. Preston, and J. J. Quinn, “A Stirling encounter with harmonic numbers,” Mathematics Magazine, vol. 75, no. 2, pp. 95–103, 2002.

L. Barrière, F. Comellas, C. Dalfó, and M. A. Fiol, “The hierarchical product of graphs,” Discrete Applied Mathematics, vol. 157, no. 1, pp. 36–48, 2009.

OEIS Foundation Inc., “Online Encyclopedia of Integer Sequences,” published electronically at http://oeis.org.

M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, “Multilayer networks,” Journal of Complex Networks, vol. 2, no. 3, pp. 203–271, 2014.

D. R. DeFord and S. D. Pauls, “A new framework for dynamical models on multiplex networks,” Journal of Complex Networks, vol. 6, no. 3, pp. 353–381, 2018.

D. R. DeFord and S. D. Pauls, “Spectral clustering methods for multiplex networks,” Physica A, vol. 533, 121949, 2019.

D. R. DeFord, “Matched products and dynamical models for multiplex networks,” Ph.D. Thesis, Dartmouth College, 2018.

R. Kennedy and K. Cooper, “Variations on a 5×5 seating rearrangement problem,” Mathematics in College, pp. 59–67, 1993.

T. Otake, R. Kennedy, and K. Cooper, “On a seating rearrangement problem,” Mathematics and Informatics Quarterly, vol. 52, pp. 63–71, 1996.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats