On the number of unlabeled vertices in edge-friendly labelings of graphs

preprint2011arXivOpen access

Abstract

Let GG be a graph with vertex set V(G)V(G) and edge set E(G)E(G), and ff be a 0-1 labeling of E(G)E(G) so that the absolute difference in the number of edges labeled 1 and 0 is no more than one. Call such a labeling ff \emph{edge-friendly}. We say an edge-friendly labeling induces a \emph{partial vertex labeling} if vertices which are incident to more edges labeled 1 than 0, are labeled 1, and vertices which are incident to more edges labeled 0 than 1, are labeled 0. Vertices that are incident to an equal number of edges of both labels we call \emph{unlabeled}. Call a procedure on a labeled graph a \emph{label switching algorithm} if it consists of pairwise switches of labels. Given an edge-friendly labeling of KnK_n, we show a label switching algorithm producing an edge-friendly relabeling of KnK_n such that all the vertices are labeled. We call such a labeling \textit{opinionated}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.