Perfect edge marking

Perfect (or graceful) marking of edges of a graph is a type of marking of a graph . This is the markup for simple graphs (in a simple graph, no two different edges connect the same two different vertices , no edge connects a vertex to it (no loops) and the graph is connected ). Perfect marking of edges was introduced in his article by S. Law ^[1] .

Content

Definition

If a graph G is given , we denote the set of vertices of the edges of the graph by E ( G ), and the set of vertices by V ( G ). Let q be the cardinality of the set E ( G ), and p be the cardinality V ( G ). If the labeling (numbering from 1 to q) of the edges is specified, the vertex u of the graph is marked with the sum of the labels of the incident edges modulo p . Or, the generated markup of the vertex u is given by the formula

V(u)=\Sigma E(e)\mod |V(G)|

{\ displaystyle V (u) = \ Sigma E (e) \ mod | V (G) |}

where V ( u ) is the label for the vertex, and E ( e ) is the assigned label value of the edge incident to u .

The task is to find the marking of the edges such that all numbers from 1 to q are used as labels once and the generated vertex labels take values from 0 to p - 1. In other words, the resulting set of labels for the edges should be $\{1,2\dots q\}$ ${\ displaystyle \ {1,2 \ dots q \}}$ and $\{0,1\dots p-1\}$ ${\ displaystyle \ {0,1 \ dots p-1 \}}$ for the peaks.

It is said that a graph G is edge-perfect if perfect marking of edges is available in it.

Examples

Paths

Imagine a path with two vertices, P ₂ . The only possible markup would be 1 as the edge label. Incidental labels of two vertices will have a value of 1. Thus, P _{2 is} not edge-perfect.

Adding an edge and a vertex to P ₂ gives P _{3 a} path with three vertices. Denote the vertices by v ₁ , v ₂ and v ₃ . We mark the edges as follows: the edge ( v ₁ , v ₂ ) is labeled 1, and the edge ( v ₂ , v ₃ ) is labeled 2. Then the generated markup of the vertices v ₁ , v ₂ and v ₃ is 1, 0 and 2, respectively. This is the perfect marking of the edges, and therefore P ₃ is edge-perfect.

Similarly, we can verify that P _{4 is} not edge-perfect.

In the general case, P _{m is} edge-perfect when m is odd, and not edge-perfect when m is odd. This follows from the necessary condition for edge perfection (see below).

Cycles

Imagine a cycle with three vertices, C ₃ . It is just a triangle. You can number the edges with numbers 1, 2, and 3 and verify that the generated vertex markup gives a perfect edge markup.

Like the ways $C_{m}$ ${\ displaystyle C_ {m}}$ edge-perfect when m is odd and imperfect when m is even.

Ribbed perfect marking $C_{5}$ ${\ displaystyle C_ {5}}$ shown in the figure:

Necessity condition

S. Law gave the necessary condition for a graph to be edge-perfect - a graph with q edges and p vertices is edge-perfect only if

\;q(q+1)

{\ displaystyle \; q (q + 1)}

comparable to

{\frac {p(p-1)}{2}}

{\ displaystyle {\ frac {p (p-1)} {2}}}

modulo p ,

or

q(q+1)\equiv {\frac {p(p-1)}{2}}\mod p.

{\ displaystyle q (q + 1) \ equiv {\ frac {p (p-1)} {2}} \ mod p.}

In the literature, this condition is called the Lo condition . This follows from the fact that the sum of the vertex labels is equal to twice the sum of the edges modulo p . The condition is useful for proving that a graph is edge-imperfect. For example, a condition can be directly applied to paths and loops.

Some other graphs

The Count of Petersen is not fin-perfect.
Star graph $S_{m}$ ${\ displaystyle S_ {m}}$ (center vertex and m rays of length 1) is edge-perfect when m is even and imperfect when m is odd.
Friendship graph $F_{m}$ ${\ displaystyle F_ {m}}$ is edge-perfect when m is odd and imperfect when m is even.
$T_{m,n}$ ${\ displaystyle T_ {m, n}}$ (with depth n , m new vertices are attached to each non-leaf vertex) is edge-perfect when m is even for any value of n , but imperfect when m is odd.
Full graph with n vertices, $K_{n}$ ${\ displaystyle K_ {n}}$ is edge-perfect if $n\neq 2\mod 4$ ${\ displaystyle n \ neq 2 \ mod 4}$ .
No staircase is a perfect edge graph.

Notes

↑ Lo, 1985 , p. 231-241.

Literature

Sheng-Ping Lo. On edge-graceful labelings of graphs. Proc. Conf., Sundance / Utah 1985 // Congressus Numerantium. - 1985.- T. 50 . - S. 231–241 .
Q. Kuan, S. Lee, J. Mitchem, A. Wang. On Edge-Graceful Unicyclic Graphs // Congressus Numerantium. - 1988 .-- T. 61 . - S. 65–74 .
L. Lee, S. Lee, G. Murty. On Edge-Graceful Labelings of Complete Graphs: Solutions of Lo's Conjecture // Congressus Numerantium. - 1988 .-- T. 62 . - S. 225–233 .
D. Small. Regular (even) Spider Graphs are Edge-Graceful // Congressus Numerantium. - 1990 .-- T. 74 . - S. 247–254 .
S. Cabaniss, R. Low, J. Mitchem. On Edge-Graceful Regular Graphs and Trees // Ars Combinatoria. - 1992 .-- T. 34 . - S. 129–142 .

[_e17c0e308f7651ab-1] Lo, 1985 , p. 231-241.