IJPAM: Volume 119, No. 4 (2018)

Title

THE FORCING EDGE STEINER NUMBER OF A GRAPH

Authors

A. Siva Jothi$^1$, J. John$^2$, S. Robinson Chellathurai$^3$
$^1$Department of Mathematics
Marthandam College of Engineering and Technology
Kuttakuzhi, 629 177, INDIA
$^2$Department of Mathematics
Government College of Engineering
Tirunelveli, 627 001, INDIA
$^3$Department of Mathematics
Scott Christian College
Nagercoil, 629 003, INDIA

Abstract

For a connected graph $G =(V,E)$, a set $W \subseteq V(G)$ is called an edge Steiner set of $G$ if every edge of $G$ is contained in a Steiner W-tree of $G$. The edge Steiner number $s_{1}(G)$ of $G$ is the minimum cardinality of its edge Steiner sets and any edge Steiner set of cardinality $s_{1}(G)$ is a minimum edge Steiner set of $G$. For a minimum edge Steiner set $W$ of $G$, a subset $T\subseteq W$ is called a forcing subset for $W$ if $W$ is the unique minimum edge Steiner set containing $T$. A forcing subset for $W$ of minimum cardinality is a minimum forcing subset of $W$. The forcing edge Steiner number of $W$, denoted by $fs_{1}(W)$, is the cardinality of a minimum forcing subset of $W$. The forcing edge Steiner number of $G$, denoted by $fs_{1}(G)$, is $fs_{1}(G)$ = $\min \lbrace fs_{1}(W) \rbrace$, where the minimum is taken over all minimum edge Steiner sets $W$ in $G$. Some general properties satisfied by this concept are studied. The forcing edge Steiner numbers of certain classes of graphs are determined. It is shown for every pair of integers with $0 \leq a \leq b$, $b \geq 2$ and $ b-a-1 > 0 $, there exists a connected graph $G$ such that $fs_{1}(G)$ = $a$ and $s_{1}(G)$ = $b$.

History

Received: August 28, 2017
Revised: August 7, 2018
Published: August 10, 2018

AMS Classification, Key Words

AMS Subject Classification: 05C12
Key Words and Phrases: Steiner distance, Steiner number, edge Steiner number, forcing Steiner number, forcing edge Steiner number

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
Buckley, F. Harary, Distance in Graphs, Addition- Wesley, Redwood City, CA, 1990.

2
G. Chartrand and P. Zhang, The Steiner number of a graph, Discrete Mathematics 242 (2002) 41 - 54.

3
G. Chartrand, P. Zhang, The Forcing Geodetic Number of a Graph, Discussiones Mathematicae Vol. 19, (1999) 45 - 58.

4
A. P. Santhakumaran and J. John, The forcing Steiner number of a graph. Discussiones Mathematicae Graph Theory 31 (1) (2011) 171-181.

5
A. P. Santhakumaran and J. John, The edge Steiner number of a graph, Journal of Discrete Mathematical Science and Cryptography Vol. 10, No. 5, (2007) 677 - 696.

5
A.P. Santhakumaran and J. John, On the forcing Geodetic and the forcing Steiner Numbers of a graph, Discussiones Mathematicae Graph Theory 31 (4) (2011), 611-624.

How to Cite?

DOI: 10.12732/ijpam.v119i4.11 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2018
Volume: 119
Issue: 4
Pages: 695 - 704


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).