Graphs With Minimal Strength

Authors Zhenbin Gao, Gee-Choon Lau, Wai Chee Shiu

Publication date 28 February 2021

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: For any graph

G

of order

p

, a bijection

f : V (G) o [1, p]

is called a numbering of the graph

G

of order

p

. The strength

s t r_{f} (G)

of a numbering

f : V (G) o [1, p]

of

G

is defined by

s t r_{f} (G) = m a x f (u) + f (v); |; u v i n E (G),

and the strength

s t r (G)

of a graph

G

itself is

s t r (G) = m i n s t r_{f} (G); |; f m b o x i s a n u m b e r i n g o f G .

A numbering

f

is called a strength labeling of

G

if

s t r_{f} (G) = s t r (G)

. In this paper, we obtained a sufficient condition for a graph to have

s t r (G) = | V (G) | + d (G)

. Consequently, many questions raised in [Bounds for the strength of graphs, {it Aust. J. Combin.} {�f72(3)}, (2018) 492--508] and [On the strength of some trees, {it AKCE Int. J. Graphs Comb.} (Online 2019) doi.org/10.1016/j.akcej.2019.06.002] are solved. Moreover, we showed that every graph

G

either has

s t r (G) = | V (G) | + d (G)

or is a proper subgraph of a graph

H

that has

s t r (H) = | V (H) | + d (H)

with

d (H) = d (G)

. Further, new good lower bounds of

s t r (G)

are also obtained. Using these, we determined the strength of 2-regular graphs and obtained new lower bounds of

s t r (Q_{n})

for various

n

, where

Q_{n}

is the

n

-regular hypercube.

This page was built for publication: Graphs With Minimal Strength

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6361777)