Forcing Parameters and Propagation Time of Certain Graph Classes

Title

Forcing Parameters and Propagation Time of Certain Graph Classes

Creator

M R, Raksha

Contributor

Dominic, Charles

Description

A branch of mathematics that treats vertices and edges of a graph is called graph theory. This theory is used to replicate many real-life situations and physical problems. Graph coloring problem is one of the prominent studies in extremal graph theory. Suppose information has to be communicated in a network or some product has to be marketed to all the people in a cluster then there are two types of cost that needs to be encountered, one the cost of selecting the initial set of vertices in a network and the second is, time it takes to propagate the information through the entire network. The sum of these two parameters is known as the total cost. Optimizing the total cost, which is the sum of vertices and the time it takes to propagate information through the entire network, is a challenging problem for any newlinegraph. Such an interesting and well-studied problem is called the dynamic coloring newlineproblem. The forcing problem also known as infecting or spreading problem is one newlinesuch dynamic coloring problem where two colors- white and black are used. Assume that a fxed set of vertices in a graph G are initially black and that the remaining vertices are considered white vertices. The aim of the forcing process is to obtain, fully black-colored vertices of the graph G by progressively applying the color change law, making sure that at least one white vertex is forced black in every discrete time interval. The forcing index is the minimum cardinality of the forcing sets. Diand#64256;erent types of forcing, such as one forcing, connected one forcing, k-forcing connected k-forcing etc., are defned based on the color change law. The one forcing is the basic form of forcing. A generalised form of one forcing is known as k-forcing where k lt V (G). The time taken by a forcing set to force the entire vertices of the graph G black is the propagation time or iteration index. The subject of study aims to fnd the one forcing number and k-forcing number of diand#64256;erent types of graph classes and derived graph classes.

Source

Author's Submission

Date

2024-01-01

Publisher

Christ(Deemed to be University)

Subject

Mathematics and Statistics

Rights

Open Access

Relation

61000309

Format

PDF

Language

English

Type

PhD

Identifier

http://hdl.handle.net/10603/547693