Page 1

Displaying 1 – 3 of 3

Showing per page

Partial covers of graphs

Jirí Fiala, Jan Kratochvíl (2002)

Discussiones Mathematicae Graph Theory

Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...

Product rosy labeling of graphs

Dalibor Fronček (2008)

Discussiones Mathematicae Graph Theory

In this paper we describe a natural extension of the well-known ρ-labeling of graphs (also known as rosy labeling). The labeling, called product rosy labeling, labels vertices with elements of products of additive groups. We illustrate the usefulness of this labeling by presenting a recursive construction of infinite families of trees decomposing complete graphs.

Currently displaying 1 – 3 of 3

Page 1