zbMATH — the first resource for mathematics

On the number of unlabeled vertices in edge-friendly labelings of graphs. (English) Zbl 1232.05205
Summary: 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 fedge-friendly. We say an edge-friendly labeling induces a 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 unlabeled. Call a procedure on a labeled graph a 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 opinionated.
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C30 Enumeration in graph theory
Full Text: DOI arXiv
[1] Cahit, I., Cordial graphs: a weaker version of graceful and harmonious graphs, Ars combinatoria, 23, 201-207, (1987) · Zbl 0616.05056
[2] Chen, B.L.; Huang, K.C.; Lee, S.M.; Liu, S.S., On edge-balanced multigraphs, Journal of combinatorial mathematics and combinatorial computing, 42, 177-185, (2002) · Zbl 1025.05053
[3] Diestel, R., Graph theory, Heidelberg graduate texts in mathematics, vol. 173, (2005), Springer-Verlag New York · Zbl 1074.05001
[4] Graham, R.L.; Sloane, N., On additive bases and harmonious graphs, SIAM journal on algebraic and discrete mathematics, 1, 382-404, (1980) · Zbl 0499.05049
[5] Kong, M.; Lee, S.M., On edge-balanced graphs, Graph theory, combinatorics and algorithms, 1, 711-722, (1995) · Zbl 0842.05077
[6] Lee, S.M.; Liu, A.; Tan, S.K., On balanced graphs, Congressus numerantium, 87, 59-64, (1992) · Zbl 0770.05086
[7] A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, NY, Dunod Paris, 1967, pp. 349-355.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.