Abstract
In this note we consider intervals and convex sets of strong product. Vertices of an arbitrary interval of \({G\boxtimes H}\) are classified with shortest path properties of one factor and a walk properties of a slightly modified second factor. The convex sets of the strong product are characterized by convexity of projections to both factors and three other local properties, one of them being 2-convexity.
Similar content being viewed by others
References
Anand B.S., Changat M., Klavžar S., Peterin I.: Convex sets in lexicographic products of graphs. Graphs Combin. 28, 77–84 (2012)
Cáceres J., Hernando M.C., Mora M., Pelayo I.M., Puertas M.L.: On the geodetic and the hull numbers in strong product graphs. Comput. Math. Appl. 60, 3020–3031 (2010)
Calder J.: Some elementary properties of interval convexities. J. London Math. Soc. 3, 422–428 (1971)
Changat M., Mathew J.: On triangle path convexity in graphs. Discret. Math. 206, 91–95 (1999)
Changat M., Mulder H.M., Sierksma G.: Convexities related to path properties on graphs. Discret. Math. 290, 117–131 (2005)
Ghidewon A.-A., Hammack R.: Centers of tensor product of graphs. Ars. Combin. 74, 201–211 (2005)
Graovac A., Pisanski T.: On the Wiener index of a graph. J. Math. Chem. 8, 53–62 (1991)
Hammack R., Imrich W., Klavžar S.: Handbook of Product Graphs, 2nd Edn. CRC Press, Boca Raton (2011)
Imrich W., Klavžar S., Rall D.F.: Topics in Graph Theory: Graphs and Their Cartesian Product. A K Peters, Wellesley (2008)
Kim S.-R.: Centers of a tensor composite graph. Congr. Numer. 81, 193–203 (1991)
Körner J., Pilotto C., Simonyi G.: Local chromatic number and Sperner capacity. J. Combin. Theory Ser. B 95, 101–117 (2005)
Král D., Maxová J., Šámal R., Podbrdský P.: Hamiltonian cycles in strong products of graphs. J. Graph Theory 48, 299–321 (2005)
Mulder, H.M.: The interval function of a graph. In: Mathematical Centre Tracts, vol. 132. Mathematisch Centrum, Amsterdam (1980)
Morgana M.A., Mulder H.M.: The induced path convexity, betweenness and svelte graphs. Discret. Math. 254, 349–370 (2002)
Santhakumaran A.P., Ullas Chandran S.V.: The geodetic number of strong product graphs. Discuss. Math. Graph Theory 30, 687–700 (2010)
Santhakumaran A.P., Ullas Chandran S.V.: The hull number of strong product graphs. Discuss. Math. Graph Theory 31, 493–507 (2011)
Špacapan S.: Connectivity of strong product of graphs. Graphs Combin. 26, 457–467 (2010)
van de Vel, M.L.J.: Theory of Convex Structures. North Holland, Amsterdam (1993)
Yeh Y.N., Gutman I.: On the sum of all distances in composite graphs. Discret. Math. 135, 359–365 (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Peterin, I. Intervals and Convex Sets in Strong Product of Graphs. Graphs and Combinatorics 29, 705–714 (2013). https://doi.org/10.1007/s00373-012-1144-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-012-1144-4