✦ LIBER ✦

Equitable labelings of cycles

✍ Scribed by Jerzy Wojciechowski

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 605 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170410

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Every labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge (x, y) is the absolute value of the difference of the labels of x and y. By analogy with graceful labelings, we say that a labeling of the vertices of a graph of order n is minimally k‐equitable if the vertices are labeled with 1,2,…, n and in the induced labeling of its edges every label either occurs exactly k times or does not occur at all. Bloom [3] posed the following question: Is the condition that k is a proper divisor of n sufficient for the cycle C~n~ to have a minimal k‐equitable labeling? We give a positive answer to this question. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Convex labelings of trees

✍ Stephen J. Dow; Douglas F. Rall; Peter J. Slater 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 456 KB

A convex labeling of a tree T o f order n is a one-to-one function f from the vertex set of Tinto the nonnegative integers, so that f ( y ) 5 ( f ( x ) t f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f (v) I n -1 for every vertex v of T, then f is a perfect convex labeling and T

Group labelings of graphs

✍ Paul H. Edelman; Michael Saks 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract Given a graph Γ an abelian group __G__, and a labeling of the vertices of Γ with elements of __G__, necessary and sufficient conditions are stated for the existence of a labeling of the edges in which the label of each vertex equals the product of the labels of its incident edges. Such

Path-sequential labellings of cycles

✍ Jeffrey M. Vanderkam 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 508 KB

We investigate labelling the vertices of the cycle of length n with the integers 0, ..., n -1 in such a way that the n sums of k adjacent integers are sequential. We show that this is impossible for both n and k even, possible for n even and k odd, and that it is possible for many cases where n is o

Equitable allocation of resources

📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 30 KB

Health care expenditures in the United States continue to rise, reaching over $1.4 trillion in 2001 (14% of the gross domestic product), with hospital spending accounting for the largest portion. Hospitals are under constant pressure to provide more efficient care with limited resources. As hospital

Equitable Coloring of Trees

✍ B.L. Chen; K.W. Lih 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 224 KB

A graph is equitably $k$-colorable if its vertices can be partitioned into $k$ independent sets of as near equal sizes as possible. Regarding a non-null tree $T$ as a bipartite graph $T(X, Y)$, we show that $T$ is equitably $k$-colorable if and only if (i) $k \geqslant 2$ when ||\(X|-|

On sequential labelings of graphs

✍ Thom Grace 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

A valuation on a simple graph G IS an assignment of labels to the vertices of G which induces an assignment of labels to the edges of G. pvaluations, also called graceful labelings, and a-valuations, a subclass of graceful labelings, have an extensive literature; harmonious labelings have been intro