95-29 Some New Graph Labeling Problems: A Preliminary Report

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