Transitivity of trees

Title

Transitivity of trees

Creator

Samuel L.C.; Joseph M.

Description

For a graph G = (V,E), a partition ? = (V1,V2,..,Vk) of the vertex set V is a transitive partition if Vi dominates Vj whenever i < j. The transitivity Tr(G) of a graph G is the maximum order of a transitive partition of V. For any positive integer k, we characterize the smallest tree with transitivity k and obtain an algorithm to determine the transitivity of any tree of finite order. 2022 World Scientific Publishing Company.

Source

Discrete Mathematics, Algorithms and Applications, Vol-14, No. 6

Date

2022-01-01

Publisher

World Scientific

Subject

domatic number; Domination; transitivity

Coverage

Samuel L.C., Department of Mathematics, Christ (Deemed to Be University), Karnataka, Bangalore, India; Joseph M., Department of Mathematics, Christ (Deemed to Be University), Karnataka, Bangalore, India

Rights

Restricted Access

Relation

ISSN: 17938309

Format

Online

Language

English

Type

Article

Identifier

https://doi.org/10.1142/S1793830922500203

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85118483102&doi=10.1142%2fS1793830922500203&partnerID=40&md5=4b286cf8054c128dd104558ebafa69a0