CONNECTED FORCING NUMBER OF CERTAIN GRAPHS

Print ISSN: 0972-7752 | Online ISSN: 2582-0850 | Total Downloads : 26

Abstract

Given a simple graph $ G=(V,E) $ with a set $ S \subseteq V $, to be an initial set of coloured vertices called black vertices and all remaining vertices being uncoloured, called white vertices. At each integer valued time step, a coloured vertex in the set $ S $ with a single uncoloured neighbour will force that neighbour to get coloured and such a vertex is called a forcing vertex and the set $ S $ is called a forcing set, if by relatively applying the forcing process, all of $ V $ becomes coloured. The forcing number of a graph $ G $ is the cardinality of the smallest forcing set of $ G $ and it is denoted by $ F(G) $. One of the variants of forcing, namely connected forcing, is a restriction of forcing in which initial set of coloured vertices induces a connected subgraph. The connected forcing number, $ F_{c}(G) $ of a graph $ G $, is the minimum cardinality among all connected forcing sets of $ G $. In this paper, we determine $ F_{c}(G) $ of degree splitting graphs and line graphs of certain graphs. Further we discuss on its bounds and the realizability theorem.

Keywords and Phrases

Forcing, Forcing number, Connected forcing, Connected forcing number, Degree splitting graphs, Line graphs.

A.M.S. subject classification

05C15, 05C69.

.....

Download PDF 26 Click here to Subscribe now