$k$-distance enclaveless number of a graph

$k$ -distance enclaveless number of a graph

Document Type : Research Articles

Authors

¹ Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

² Department of Mathematics, Tafresh University, Tafresh, Iran

Abstract

For an integer

k \geq 1

, a

k

-distance enclaveless number (or

k

-distance

B

-differential) of a connected graph

G = (V, E)

Ψ^{k} (G) = m a x {| (V - X) \cap N_{k, G} (X) | : X \subseteq V}

. In this paper, we establish upper bounds on
the

k

-distance enclaveless number of a graph in terms of its diameter, radius and girth. Also, we
prove that for connected graphs

G

and

H

with orders

n

and

m

respectively,

Ψ^{k} (G \times H) \leq m n - n - m + Ψ^{k} (G) + Ψ^{k} (H) + 1

, where

G \times H

denotes the direct product of

G

and

H

.
In the end of this paper, we show that the

k

-distance enclaveless number

Ψ^{k} (T)

of a tree

T

n \geq k + 1

vertices and with

n_{1}

leaves satisfies inequality

Ψ^{k} (T) \leq \frac{k (2 n - 2 + n_{1})}{2 k + 1}

and we characterize the extremal trees.

Keywords