Digital repository of Slovenian research organisations

Search the repository
A+ | A- | Help | SLO | ENG

Query: search in
search in
search in
search in

Options:
  Reset


Query: "keywords" (Cartesian product of graphs) .

1 - 2 / 2
First pagePrevious page1Next pageLast page
1.
General position polynomials
Vesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite, 2024, original scientific article

Abstract: A subset of vertices of a graph $G$ is a general position set if no triple of vertices from the set lie on a common shortest path in $G$. In this paper we introduce the general position polynomial as $\sum_{i \geq 0} a_i x^i$, where $a_i$ is the number of distinct general position sets of $G$ with cardinality $i$. The polynomial is considered for several well-known classes of graphs and graph operations. It is shown that the polynomial is not unimodal in general, not even on trees. On the other hand, several classes of graphs, including Kneser graphs $K(n,2)$, with unimodal general position polynomials are presented.
Keywords: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs
Published in DiRROS: 28.02.2024; Views: 123; Downloads: 84
.pdf Full text (384,07 KB)
This document has many files! More...

2.
Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problem
Sandi Klavžar, Eva Zmazek, 2024, original scientific article

Abstract: A set of vertices $X$ of a graph $G$ is a strong edge geodetic set if to any pair of vertices from $X$ we can assign one (or zero) shortest path between them such that every edge of $G$ is contained in at least one on these paths. The cardinality of a smallest strong edge geodetic set of $G$ is the strong edge geodetic number ${\rm sg_e}(G)$ of $G$. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs $G$ with ${\rm sg_e}(G) = n(G)$ are characterized and ${\rm sg_e}$ is determined for Cartesian products $P_n\,\square\, K_m$. The latter result in particular corrects an error from the literature.
Keywords: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs
Published in DiRROS: 19.02.2024; Views: 153; Downloads: 52
.pdf Full text (430,75 KB)
This document has many files! More...
Search done in 0.05 sec.
Back to top