Linear Forest <i>mP</i>₃ Plus a Longer Path <i>P</i>_n Becoming Antimagic

Abstract

An edge labeling of a graph G is a bijection f from E(G) to a set of |E(G)| integers. For a vertex u in G, the induced vertex sum of u, denoted by f+(u), is defined as f+(u)=∑uv∈E(G)f(uv). Graph G is said to be antimagic if it has an edge labeling g such that g(E(G))={1,2,⋯,|E(G)|} and g+(u)≠g+(v) for any pair u,v∈V(G) with u≠v. A linear forest is a union of disjoint paths of orders greater than one. Let mPk denote a linear forest consisting of m disjoint copies of path Pk. It is known that mP3 is antimagic if and only if m=1. In this study, we add a disjoint path Pn (n≥4) to mP3 and develop a necessary condition and a sufficient condition whereby the new linear forest mP3⋃Pn may be antimagic.

Keywords

• edge labeling
• antimagic labeling
• antimagic graph
• disconnected antimagic graph
• linear forest