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.

    Comment: 9 pages, 1 figure

    https://doi.org/10.46298/dmtcs.7627
    Source: arXiv.org:2009.08787
    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
    Licence: arXiv.org - Non-exclusive license to distribute

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Share and export

    Consultation statistics

    This page has been seen 1169 times.
    This article's PDF has been downloaded 944 times.