DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

M. Ghorbani, H.R. Maimani, M. Momeni, F. Rahimi Mahid, S. Klavžar, G. Rus

Title:

The general position problem on Kneser graphs and on some graph operations

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-03-11, Revised: 2019-11-13, Accepted: 2019-11-20, https://doi.org/10.7151/dmgt.2269

Abstract:

A vertex subset $S$ of a graph $G$ is a general position set of $G$ if no vertex of $S$ lies on a geodesic between two other vertices of $S$. The cardinality of a largest general position set of $G$ is the general position number (gp-number) $gp(G)$ of $G$. The gp-number is determined for some families of Kneser graphs, in particular for $K(n,2)$, $n\ge 4$, and $K(n,3)$, $n\ge 9$. A sharp lower bound on the gp-number is proved for Cartesian products of graphs. The gp-number is also determined for joins of graphs, coronas over graphs, and line graphs of complete graphs.

Keywords:

general position set, Kneser graphs, Cartesian product of graphs, corona over graphs, line graphs

PDF
Close