## DIMACS TR: 95-29

## Some New Graph Labeling Problems: A Preliminary Report

### Author: Stephen Penrice

**
ABSTRACT
**

All "labelings" discussed in this paper are vertex labelings. We
call a labeling $1$ of $G$ an $N$-labeling if there exists a connected
induced subgraph $H$ of $G$ with $\sum_{x \in V(H)}1(x) = i$ for every
integer $i$, $1 \leq i \leq N$. Then $\sigma_c(G)$ is the largest
integer $N$ such that $G$ has an $N$-labeling. A labeling $1$ of $G$
is called {\em irredundant\/} if, for all connected induced subgraphs
$H_1$ and $H_2$, $\sum_{x \in V(H_1)}1(x) = \sum_{x \in V(H_2)}1(x)$
if and only if $H_1 = H_2$. Then $\sigma_p(G)$ is the smallest
integer $N$ such that there exists an irredundant labeling $1$ of $G$
with $\sum_{x \in V(G)}1(x) = N$. In this report, we study
$\sigma_c(G)$ and $\sigma_p(G)$ in the cases where $G$ is a complete
graph minus one edge, a star, a path, or a cycle. We obtain some
preliminary results, but there are many interesting questions left
open.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-29.ps.gz

DIMACS Home Page