Catálogo de publicaciones - libros

A graph = (,) is called a split graph if there exists a partition = ∪ such that the subgraphs [ ] and [] of induced by and are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for split graphs with | |<|| to be hamiltonian. This condition is not sufficient. In this paper, we give two constructions for producing infinite families of split graphs with | |<||, which satisfy the Burkard-Hammer condition but have no Hamilton cycles.

We consider the problem of searching for a moving target with unbounded speed in a dark polygonal region by a searcher. The searcher continuously moves on the polygon boundary and can see only along the rays of the flashlights emanating from his position at a time. We present necessary and sufficient conditions for a polygon of vertices to be . Our two main results are the following:

A mapping is called a sum labeling of a graph ((),()) if it is an injection from () to a set of positive integers, such that ∈ () if and only if there exists a vertex ∈ () such that () = () + (). In this case, is called a . We define as of a graph if it is a sum labeling of for some non negative integer , and contains no working vertex. In general, a graph will require some isolated vertices to be labeled exclusively. The least possible number of such isolated vertices is called of ; denoted by ().

An exclusive sum labeling of a graph is said to be if it labels exclusively by using () isolated vertices. In case () = Δ (), where Δ() denotes the maximum degree of vertices in , the labeling is called Δ.

In this paper we present Δ-optimum exclusive sum labeling of certain graphs with radius one, that is, graphs which can be obtained by joining all vertices of an integral sum graph to another vertex. This class of graphs contains infinetely many graphs including some populer graphs such as wheels, fans, friendship graphs, generalised friendship graphs and multicone graphs.