On the Existence of Constrained Labelling of Locally Finite Graphs

摘要

A labelling of a graph G = (V, E) over a field F, is a mapping of the edge set of the graph into F. A sequence r = (r(v))_(v∈V) where r(v) e F, for all v ∈ V is called a constrained sequence of G over F. A labelling f of G is called a constrained labelling corresponding to the constrained sequence r, if the sum of the labels of the edges incident to v is r(v), for all v G V. For finite graphs, the existence of constrained labellings correspopnding to a given constrained sequence was extensively studied by various author. It depend on whether the graph considered is bipartite or not, as well as some specific condition on the constrained sequence. In this paper, we discuss the existence of constrained labellings for locally finite graphs. We have noticed that given any constrained sequence for a locally finite graph, a constrained labelling does exist always. The proof is constructive in nature and uses famous Konig's Infinity Lemma and a lemma of our own which seem to be interesting in it's own right. These studies open the door of generalizing the concept of magicness of finite graphs to infinite graphs.