Page 1

Displaying 1 – 4 of 4

Showing per page

Interval edge colorings of some products of graphs

Petros A. Petrosyan (2011)

Discussiones Mathematicae Graph Theory

An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,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 ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product of these graphs...

Interval Edge-Colorings of Cartesian Products of Graphs I

Petros A. Petrosyan, Hrant H. Khachatrian, Hovhannes G. Tananyan (2013)

Discussiones Mathematicae Graph Theory

A proper edge-coloring of a graph G with colors 1, . . . , t is an interval t-coloring if all colors are used and the colors of edges incident to each vertex of G form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. Let [...] be the set of all interval colorable graphs. For a graph G ∈ [...] , the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W(G), respectively. In this paper...

Iterated neighborhood graphs

Martin Sonntag, Hanns-Martin Teichert (2012)

Discussiones Mathematicae Graph Theory

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph ( V , E N ) where E N = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph N k ( G ) : = N ( N ( . . . N ( G ) ) ) of G. In particular we investigate conditions for G and k such that N k ( G ) becomes a complete graph.

Currently displaying 1 – 4 of 4

Page 1