Abstract
In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some products. One of our main result is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in quasi-linear time. Both these results use their counterparts for ordinary graphs as building blocks. We also study the signed chromatic number of graphs with underlying graph of the form \(P_n \ \square \ P_m\), of products of signed paths, of products of signed complete graphs and of products of signed cycles, that is the minimum order of a signed graph to which they admit a homomorphism.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aurenhammer, F., Hagauer, J., Imrich, W.: Cartesian graph factorization at logarithmic cost per edge. Comput. Complex. 2(4), 331–349 (1992)
Bondy, J.A., Murty, U.S.R.: Graph Theory, 1st edn. Springer, Dordrecht (2008). https://doi.org/10.1007/978-1-4020-6754-9
Feder, T.: Product graph representations. J. Graph Theory 16(5), 467–488 (1992)
Feigenbaum, J., Hershberger, J., Schäffer, A.A.: A polynomial time algorithm for finding the prime factors of cartesian-product graphs. Discrete Appl. Math. 12(2), 123–138 (1985)
Fernández, A., Leighton, T., López-Presa, J.L.: Containment properties of product and power graphs. Discrete Appl. Math. 155(3), 300–311 (2007)
Germina, K.A., Hameed K, S., Zaslavsky, T.: On products and line graphs of signed graphs, their eigenvalues and energy. Linear Algebra Appl. 435(10), 2432–2450 (2011). Special Issue in Honor of Dragos Cvetkovic
Guenin, B.: Packing odd circuit covers: a conjecture. Manuscript (2005)
Harary, F.: On the notion of balance of a signed graph. Michigan Math. J. 2(2), 143–146 (1953)
Imrich, W., Klavžar, S.: Product Graphs, Structure and Recognition, January 2000
Imrich, W., Klavžar, S., Rall, D.F.: Cancellation properties of products of graphs. Discrete Appl. Math. 155(17), 2362–2364 (2007)
Imrich, W., Peterin, I.: Recognizing cartesian products in linear time. Discrete Math. 307(3), 472–483 (2007). Algebraic and Topological Methods in Graph Theory
Imrich, W., Peterin, I.: Cartesian products of directed graphs with loops. Discrete Math. 341(5), 1336–1343 (2018)
Jacques, F., Montassier, M., Pinlou, A.: The chromatic number and switching chromatic number of 2-edge-colored graphs of bounded degree. Private communication
Naserasr, R., Rollová, E., Sopena, É.: Homomorphisms of signed graphs. J. Graph Theory 79(3), 178–212 (2015)
Sabidussi, G.: Graphs with given group and given graph theoretical properties. Canad. J. Math 9, 515–525 (1957)
Sabidussi, G.: Graph multiplication. Mathematische Zeitschrift 72, 446–457 (1959/60)
Vizing, V.G.: The cartesian product of graphs (russian). Vycisl. Sistemy 9, 30–43 (1963)
Winkler, P.: Factoring a graph in polynomial time. Eur. J. Comb. 8(2), 209–212 (1987)
Zaslavsky, T.: Signed graphs. Discrete Appl. Math. 4(1), 47–74 (1982)
Acknowledgements
We would like to thank Hervé Hocquard and Éric Sopena for their helpful comments through the making of this paper. We would also like to thank the reviewers for their comments and especially Reviewer 2 for pointing us to the techniques of [12] which could improve our algorithm.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Lajou, D. (2020). On Cartesian Products of Signed Graphs. In: Changat, M., Das, S. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2020. Lecture Notes in Computer Science(), vol 12016. Springer, Cham. https://doi.org/10.1007/978-3-030-39219-2_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-39219-2_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39218-5
Online ISBN: 978-3-030-39219-2
eBook Packages: Computer ScienceComputer Science (R0)