Rainbow connection and graph products

DOI10.1007/s00373-013-1295-yzbMath1291.05064MaRDI QIDQ2014711

Gašper Mekiš, Iztok Peterin, Tanja Gologranc

Publication date: 16 June 2014

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-013-1295-y

zbMATH Keywords

strong product; direct product; lexicographic product; (strong) rainbow connection number

Mathematics Subject Classification ID

05C38: Paths and cycles

05C15: Coloring of graphs and hypergraphs

05C40: Connectivity

05C76: Graph operations (line graphs, products, etc.)

Related Items

The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths, Rainbow connection number of comb product of graphs, Rainbow connection number of generalized composition, (Strong) rainbow connection on the splitting of 3-path, Edge-transitive lexicographic and Cartesian products, Rainbow connection number of graph power and graph products, The vertex-rainbow connection number of some graph operations, Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph, Rainbow connection number and graph operations, The rainbow connection number of the power graph of a finite group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness and algorithms for rainbow connection
• Rainbow generalizations of Ramsey theory: A survey
• Convex sets in lexicographic products of graphs
• On rainbow connection
• A note on the connectivity of Kronecker products of graphs
• Rainbow connections of graphs: a survey
• Connectivity of strong products of graphs
• Intervals and convex sets in strong product of graphs
• On the rainbow connection of Cartesian products and their subgraphs
• The rainbow connectivity of a graph
• Bounds for the rainbow connection number of graphs
• The Kronecker Product of Graphs
• Rainbow connection in graphs
• ON THE EDGE-CONNECTIVITY OF CARTESIAN PRODUCT GRAPHS
• Game coloring the Cartesian product of graphs
• Rainbow Connection in Graphs with Minimum Degree Three
• Isomorphic components of Kronecker product of bipartite graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Small cycle double covers of products I: Lexicographic product with paths and cycles