Mathematics – Combinatorics
Scientific paper
2011-03-26
Mathematics
Combinatorics
7 pages, accepted to Discrete Mathematics, special issue dedicated to Combinatorics 2010
Scientific paper
10.1016/j.disc.2011.04.005
Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$, and $f$ be a 0-1 labeling of $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 $f$ \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 $K_n$, we show a label switching algorithm producing an edge-friendly relabeling of $K_n$ such that all the vertices are labeled. We call such a labeling \textit{opinionated}.
Krop Elliot
Lee Sin-Min
Raridan Christopher
No associations
LandOfFree
On the number of unlabeled vertices in edge-friendly labelings of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the number of unlabeled vertices in edge-friendly labelings of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of unlabeled vertices in edge-friendly labelings of graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-223813