Computer Science – Discrete Mathematics
Scientific paper
2009-11-23
Computer Science
Discrete Mathematics
14 pages, 5 figures, minor changes
Scientific paper
An edge coloring of a graph $G$ with colors $1,2,\ldots ,t$ is called an interval $t$-coloring if for each $i\in \{1,2,\ldots,t\}$ there is at least one edge of $G$ colored by $i$, and the colors of edges incident to any vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable, if there is an integer $t\geq 1$ for which $G$ has an interval $t$-coloring. Let $\mathfrak{N}$ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if $G,H\in \mathfrak{N}$, then the Cartesian product of these graphs belongs to $\mathfrak{N}$. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if $G\in \mathfrak{N}$, then $G[nK_{1}]\in \mathfrak{N}$ for any $n\in \mathbf{N}$. Furthermore, we show that if $G,H\in \mathfrak{N}$ and $H$ is a regular graph, then strong and lexicographic products of graphs $G,H$ belong to $\mathfrak{N}$. We also prove that tensor and strong tensor products of graphs $G,H$ belong to $\mathfrak{N}$ if $G\in \mathfrak{N}$ and $H$ is a regular graph.
No associations
LandOfFree
Interval edge colorings of some products of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Interval edge colorings of some products of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interval edge colorings of some products of graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-173532