Angsuman Das ; Hiranya Kishore Dey - Determining Number of Kneser Graphs: Exact Values and Improved Bounds

dmtcs:7627 - Discrete Mathematics & Theoretical Computer Science, March 30, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.7627
Determining Number of Kneser Graphs: Exact Values and Improved BoundsArticle

Authors: Angsuman Das ; Hiranya Kishore Dey

    The determining number of a graph $G = (V,E)$ is the minimum cardinality of a set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is trivial. In this paper, we provide some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we provide the exact value of the determining number for some subfamilies of Kneser graphs.


    Volume: vol. 24, no. 1
    Section: Graph Theory
    Published on: March 30, 2022
    Accepted on: February 16, 2022
    Submitted on: June 29, 2021
    Keywords: Mathematics - Combinatorics,05C25

    Consultation statistics

    This page has been seen 879 times.
    This article's PDF has been downloaded 743 times.