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

DOI10.1016/J.DISC.2011.04.005MaRDI QIDQ658097zbMATH OpenOpenAlexFDO

Authors Elliot Krop, Christopher Raridan, Sin-Min Lee

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

partial vertex labeling

Mathematics Subject Classification ID

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

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}.

Recommendations

• scientific article; zbMATH DE number 5543097
• 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

Cites work

• scientific article; zbMATH DE number 125598 (Why is no real title available?)
• scientific article; zbMATH DE number 3997850 (Why is no real title available?)
• scientific article; zbMATH DE number 1874378 (Why is no real title available?)
• scientific article; zbMATH DE number 861312 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3308125 (Why is no real title available?)
• On Additive Bases and Harmonious Graphs

Cited in

(3)

• scientific article; zbMATH DE number 6605161 (Why is no real title available?)
• Graphs without gap-vertex-labellings: families and bounds
• Fast sequential and parallel vertex relabelings of \({K_{m,m}}\)

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)