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

DOI10.1016/J.DISC.2011.04.005zbMATH Open1232.05205arXiv1103.5127OpenAlexW1976041055MaRDI QIDQ658097FDOQ658097

Elliot Krop, Sin-Min Lee, Christopher Raridan

Publication date: 11 January 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: 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 extit{opinionated}.

Full work available at URL: https://arxiv.org/abs/1103.5127

Recommendations

• scientific article
• Edge friendly labelings of graph. I.
• scientific article; zbMATH DE number 7274720
• Full edge-friendly index sets of complete bipartite graphs
• Full-edge friendly index sets of fan

zbMATH Keywords

partial vertex labeling

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)
• On Additive Bases and Harmonious Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• Graphs without gap-vertex-labellings: families and bounds
• Title not available (Why is that?)

This page was built for publication: On the number of unlabeled vertices in edge-friendly labelings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658097)