Symmetry

Research

12 pages, 289 KiB

Open AccessArticle

Antimagic Labeling for Product of Regular Graphs

by Vinothkumar Latchoumanane and Murugan Varadhan

Symmetry 2022, 14(6), 1235; https://doi.org/10.3390/sym14061235 - 14 Jun 2022

Cited by 3 | Viewed by 5517

Abstract

An antimagic labeling of a graph

G = (V, E)

is a bijection from the set of edges of G to

\{1, 2, \dots, |E (G)|\}

and such that any two vertices of G have [...] Read more.

An antimagic labeling of a graph

G = (V, E)

is a bijection from the set of edges of G to

\{1, 2, \dots, |E (G)|\}

and such that any two vertices of G have distinct vertex sums where the vertex sum of a vertex v in

V (G)

is nothing but the sum of all the incident edge labeling of G. In this paper, we discussed the antimagicness of rooted product and corona product of graphs. We proved that if we let G be a connected t-regular graph and H be a connected k-regular graph, then the rooted product of graph G and H admits antimagic labeling if

t \geq k

. Moreover, we proved that if we let G be a connected t-regular graph and H be a connected k-regular graph, then the corona product of graph G and H admits antimagic labeling for all

t, k \geq 2

. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

10 pages, 422 KiB

Open AccessArticle

Open Support of Hypergraphs under Addition

by Shufei Wu and Mengyuan Wang

Symmetry 2022, 14(4), 669; https://doi.org/10.3390/sym14040669 - 24 Mar 2022

Cited by 2 | Viewed by 1637

Abstract

For a vertex v in a graph G, the open support of v under addition is the sum of degrees of all its neighbors. The open support of G under addition is the sum of open supports of all its vertices. The [...] Read more.

For a vertex v in a graph G, the open support of v under addition is the sum of degrees of all its neighbors. The open support of G under addition is the sum of open supports of all its vertices. The results for open support of graphs are deeply dependent on the structure property of the graph considered, such as its symmetry. In this paper, we generalize the concept of open support to hypergraphs. We give some examples and prove a general formula for open support of hypergraphs by using the adjacency and incidence matrices method. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

9 pages, 248 KiB

Open AccessArticle

D-Magic Oriented Graphs

by Alison Marr and Rinovia Simanjuntak

Symmetry 2021, 13(12), 2261; https://doi.org/10.3390/sym13122261 - 27 Nov 2021

Cited by 3 | Viewed by 1898

Abstract

In this paper, we define D-magic labelings for oriented graphs where D is a distance set. In particular, we label the vertices of the graph with distinct integers

{1, 2, \dots, | V (G) |}

[...] Read more.

In this paper, we define D-magic labelings for oriented graphs where D is a distance set. In particular, we label the vertices of the graph with distinct integers

{1, 2, \dots, | V (G) |}

in such a way that the sum of all the vertex labels that are a distance in D away from a given vertex is the same across all vertices. We give some results related to the magic constant, construct a few infinite families of D-magic graphs, and examine trees, cycles, and multipartite graphs. This definition grew out of the definition of D-magic (undirected) graphs. This paper explores some of the symmetries we see between the undirected and directed version of D-magic labelings. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

15 pages, 683 KiB

Open AccessArticle

Another Antimagic Conjecture

by Rinovia Simanjuntak, Tamaro Nadeak, Fuad Yasin, Kristiana Wijaya, Nurdin Hinding and Kiki Ariyanti Sugeng

Symmetry 2021, 13(11), 2071; https://doi.org/10.3390/sym13112071 - 2 Nov 2021

Cited by 4 | Viewed by 2255

Abstract

An antimagic labeling of a graph G is a bijection

f : E (G) \to {1, \dots, | E (G) |}

such that the weights [...] Read more.

An antimagic labeling of a graph G is a bijection

f : E (G) \to {1, \dots, | E (G) |}

such that the weights

w (x) = \sum_{y \sim x} f (y)

distinguish all vertices. A well-known conjecture of Hartsfield and Ringel (1990) is that every connected graph other than

K_{2}

admits an antimagic labeling. For a set of distances D, a D-antimagic labeling of a graph G is a bijection

f : V (G) \to {1, \dots, | V (G) |}

such that the weight

ω (x) = \sum_{y \in N_{D} (x)} f (y)

is distinct for each vertex x, where

N_{D} (x) = {y \in V (G) | d (x, y) \in D}

is the D-neigbourhood set of a vertex x. If

N_{D} (x) = r

, for every vertex x in G, a graph G is said to be $(D, r)$ -regular. In this paper, we conjecture that a graph admits a D-antimagic labeling if and only if it does not contain two vertices having the same D-neighborhood set. We also provide evidence that the conjecture is true. We present computational results that, for

D = {1}

, all graphs of order up to 8 concur with the conjecture. We prove that the set of

(D, r)

-regular D-antimagic graphs is closed under union. We provide examples of disjoint union of symmetric

(D, r)

-regular that are D-antimagic and examples of disjoint union of non-symmetric non-

(D, r)

-regular graphs that are D-antimagic. Furthermore, lastly, we show that it is possible to obtain a D-antimagic graph from a previously known distance antimagic graph. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

17 pages, 1318 KiB

Open AccessArticle

On Forbidden Subgraphs of (K₂, H)-Sim-(Super)Magic Graphs

by Yeva Fadhilah Ashari, A.N.M. Salman and Rinovia Simanjuntak

Symmetry 2021, 13(8), 1346; https://doi.org/10.3390/sym13081346 - 26 Jul 2021

Cited by 3 | Viewed by 2270

Abstract

A graph G admits an H-covering if every edge of G belongs to a subgraph isomorphic to a given graph H. G is said to be H-magic if there exists a bijection [...] Read more.

A graph G admits an H-covering if every edge of G belongs to a subgraph isomorphic to a given graph H. G is said to be H-magic if there exists a bijection

f : V (G) \cup E (G) \to {1, 2, \dots, | V (G) | + | E (G) |}

such that

w_{f} (H^{'}) = \sum_{v \in V (H^{'})} f (v) + \sum_{e \in E (H^{'})} f (e)

is a constant, for every subgraph

H^{'}

isomorphic to H. In particular, G is said to be H-supermagic if

f (V (G)) = {1, 2, \dots, | V (G) |}

. When H is isomorphic to a complete graph

K_{2}

, an H-(super)magic labeling is an edge-(super)magic labeling. Suppose that G admits an F-covering and H-covering for two given graphs F and H. We define G to be

(F, H)

-sim-(super)magic if there exists a bijection

f^{'}

that is simultaneously F-(super)magic and H-(super)magic. In this paper, we consider

(K_{2}, H)

-sim-(super)magic where H is isomorphic to three classes of graphs with varied symmetry: a cycle which is symmetric (both vertex-transitive and edge-transitive), a star which is edge-transitive but not vertex-transitive, and a path which is neither vertex-transitive nor edge-transitive. We discover forbidden subgraphs for the existence of

(K_{2}, H)

-sim-(super)magic graphs and classify classes of

(K_{2}, H)

-sim-(super)magic graphs. We also derive sufficient conditions for edge-(super)magic graphs to be

(K_{2}, H)

-sim-(super)magic and utilize such conditions to characterize some

(K_{2}, H)

-sim-(super)magic graphs. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

18 pages, 381 KiB

Open AccessArticle

On SD-Prime Labelings of Some One Point Unions of Gears

by Wai-Chee Shiu and Gee-Choon Lau

Symmetry 2021, 13(5), 849; https://doi.org/10.3390/sym13050849 - 11 May 2021

Cited by 1 | Viewed by 1904

Abstract

Let

G = (V (G), E (G))

be a simple, finite and undirected graph of order n. Given a bijection

f : V (G) \to {1, \dots, n}

, [...] Read more.

Let

G = (V (G), E (G))

be a simple, finite and undirected graph of order n. Given a bijection

f : V (G) \to {1, \dots, n}

, and every edge

u v

in

E (G)

, let

S = f (u) + f (v)

and

D = | f (u) - f (v) |

. The labeling f induces an edge labeling

f^{'} : E (G) \to {0, 1}

such that for an edge

u v

in

E (G)

,

f^{'} (u v) = 1

if

g c d (S, D) = 1

, and

f^{'} (u v) = 0

otherwise. Such a labeling is called an SD-prime labeling if

f^{'} (u v) = 1

for all

u v \in E (G)

. We provide SD-prime labelings for some one point unions of gear graphs. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

13 pages, 329 KiB

Open AccessArticle

The Irregularity and Modular Irregularity Strength of Fan Graphs

by Martin Bača, Zuzana Kimáková, Marcela Lascsáková and Andrea Semaničová-Feňovčíková

Symmetry 2021, 13(4), 605; https://doi.org/10.3390/sym13040605 - 6 Apr 2021

Cited by 17 | Viewed by 2766

Abstract

For a simple graph G with no isolated edges and at most, one isolated vertex, a labeling

φ : E (G) \to {1, 2, \dots, k}

of positive integers to the edges of G is called [...] Read more.

For a simple graph G with no isolated edges and at most, one isolated vertex, a labeling

φ : E (G) \to {1, 2, \dots, k}

of positive integers to the edges of G is called irregular if the weights of the vertices, defined as

w t_{φ} (v) = \sum_{u \in N (v)} φ (u v)

, are all different. The irregularity strength of a graph G is known as the maximal integer k, minimized over all irregular labelings, and is set to ∞ if no such labeling exists. In this paper, we determine the exact value of the irregularity strength and the modular irregularity strength of fan graphs. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

15 pages, 447 KiB

Open AccessArticle

Graphs with Minimal Strength

by Zhen-Bin Gao, Gee-Choon Lau and Wai-Chee Shiu

Symmetry 2021, 13(3), 513; https://doi.org/10.3390/sym13030513 - 21 Mar 2021

Cited by 5 | Viewed by 1960

Abstract

For any graph G of order p, a bijection

f : V (G) \to {1, 2, \dots, p}

is called a numbering of G. The strength

s t r_{f} (G)

of [...] Read more.

For any graph G of order p, a bijection

f : V (G) \to {1, 2, \dots, p}

is called a numbering of G. The strength

s t r_{f} (G)

of a numbering f of G is defined by

s t r_{f} (G) = max {f (u) + f (v) | u v \in E (G)},

and the strength

s t r (G)

of a graph G is

s t r (G) = min {s t r_{f} (G) | f is a numbering of G} .

In this paper, many open problems are solved, and the strengths of new families of graphs are determined. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

11 pages, 339 KiB

Open AccessArticle

H-Irregularity Strengths of Plane Graphs

by Martin Bača, Nurdin Hinding, Aisha Javed and Andrea Semaničová-Feňovčíková

Symmetry 2021, 13(2), 229; https://doi.org/10.3390/sym13020229 - 30 Jan 2021

Cited by 2 | Viewed by 1828

Abstract

Graph labeling is the mapping of elements of a graph (which can be vertices, edges, faces or a combination) to a set of numbers. The mapping usually produces partial sums (weights) of the labeled elements of the graph, and they often have an [...] Read more.

Graph labeling is the mapping of elements of a graph (which can be vertices, edges, faces or a combination) to a set of numbers. The mapping usually produces partial sums (weights) of the labeled elements of the graph, and they often have an asymmetrical distribution. In this paper, we study vertex–face and edge–face labelings of two-connected plane graphs. We introduce two new graph characteristics, namely the vertex–face H-irregularity strength and edge–face H-irregularity strength of plane graphs. Estimations of these characteristics are obtained, and exact values for two families of graphs are determined. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure 1

6 pages, 241 KiB

Open AccessArticle

Modular Edge-Gracefulness of Graphs without Stars

by Sylwia Cichacz and Karolina Szopa

Symmetry 2020, 12(12), 2013; https://doi.org/10.3390/sym12122013 - 6 Dec 2020

Cited by 1 | Viewed by 1404

Abstract

We investigate the modular edge-gracefulness

k (G)

of a graph, i.e., the least integer k such that taking a cyclic group

Z_{k}

of order k, there exists a function

f : E (G) \to Z_{k}

so [...] Read more.

We investigate the modular edge-gracefulness

k (G)

of a graph, i.e., the least integer k such that taking a cyclic group

Z_{k}

of order k, there exists a function

f : E (G) \to Z_{k}

so that the sums of edge labels incident with every vertex are distinct. So far the best upper bound on

k (G)

for a general graph G is

2 n

, where n is the order of G. In this note we prove that if G is a graph of order n without star as a component then

k (G) = n

for

n \neg \equiv 2 (mod 4)

and

k (G) = n + 1

otherwise. Moreover we show that for such G for every integer

t \geq k (G)

there exists a

Z_{t}

-irregular labeling. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

17 pages, 296 KiB

Open AccessArticle

Local Super Antimagic Total Labeling for Vertex Coloring of Graphs

by Slamin Slamin, Nelly Oktavia Adiwijaya, Muhammad Ali Hasan, Dafik Dafik and Kristiana Wijaya

Symmetry 2020, 12(11), 1843; https://doi.org/10.3390/sym12111843 - 7 Nov 2020

Cited by 11 | Viewed by 2955

Abstract

Let

G = (V, E)

be a graph with vertex set V and edge set E. A local antimagic total vertex coloring f of a graph G with vertex-set V and edge-set E is an injective map from [...] Read more.

Let

G = (V, E)

be a graph with vertex set V and edge set E. A local antimagic total vertex coloring f of a graph G with vertex-set V and edge-set E is an injective map from

V \cup E

to

{1, 2, \dots, | V | + | E |}

such that if for each

u v \in E (G)

then

w (u) \neq w (v)

, where

w (u) = \sum_{u v \in E (G)} f (u v) + f (u)

. If the range set f satisfies

f (V) = {1, 2, \dots, | V |}

, then the labeling is said to be local super antimagic total labeling. This labeling generates a proper vertex coloring of the graph G with the color

w (v)

assigning the vertex v. The local super antimagic total chromatic number of graph G,

χ_{l s a t} (G)

is defined as the least number of colors that are used for all colorings generated by the local super antimagic total labeling of G. In this paper we investigate the existence of the local super antimagic total chromatic number for some particular classes of graphs such as a tree, path, cycle, helm, wheel, gear, sun, and regular graphs as well as an amalgamation of stars and an amalgamation of wheels. Full article

(This article belongs to the Special Issue Graph Labelings and Their Applications)

► Show Figures

Figure A1

Journal Menu

Journal Browser

Graph Labelings and Their Applications

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Published Papers (11 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI