Browsing by Author "Peterin, Iztok"

Now showing 1 - 4 of 4

Access status: Open Access ,
A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices
(Wydawnictwa AGH, 2020) Ghareghani, Narges; Peterin, Iztok; Sharifani, Pouyeh
A subset $D$ of the vertex set $V$ of a graph $G$ is called an $[1,k]$-dominating set if every vertex from $V-D$ is adjacent to at least one vertex and at most $k$ vertices of $D$. A $[1,k]$-dominating set with the minimum number of vertices is called a $\gamma_{[1,k]}$-set and the number of its vertices is the $[1,k]$-domination number $\gamma_{[1,k]}(G)$ of $G$. In this short note we show that the decision problem whether $\gamma_{[1,k]}(G)=n$ is an $NP$-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph $G$ of order $n$ satisfying $\gamma_{[1,k]}(G)=n$ is given for every integer $n \geq (k+1)(2k+3)$.
Access status: Open Access ,
Convex geometries yielded by transit functions
(Wydawnictwa AGH, 2025) Changat, Manoj; Sheela, Lekshmi Kamal K.; Peterin, Iztok; Shanavas, Ameera Vaheeda
Let $V$ be a finite nonempty set. A transit function is a map $R:V\times V\rightarrow 2^V$ such that $R(u,u)=\{u\}$, $R(u,v)=R(v,u)$ and $u\in R(u,v)$ holds for every $u,v\in V$. A set $K\subseteq V$ is $R$-convex if $R(u,v)\subset K$ for every $u,v\in K$ and all $R$-convex subsets of $V$ form a convexity $\mathcal{C}_R$. We consider the Minkowski-Krein-Milman property that every $R$-convex set $K$ in a convexity $\mathcal{C}_R$ is the convex hull of the set of extreme points of $K$ from axiomatic point of view and present a characterization of it. Later we consider several well-known transit functions on graphs and present the use of the mentioned characterizations on them.
Access status: Open Access ,
The complexity of open k-monopolies in graphs for negative k
(Wydawnictwa AGH, 2019) Peterin, Iztok
Let $G$ be a graph with vertex set $V(G)$, $\delta(G)$ minimum degree of $G$ and $k\in\left\{1-\left\lceil\frac{\delta(G)}{2}\right\rceil,\ldots ,\left\lfloor \frac{\delta(G)}{2}\right\rfloor\right\}$. Given a nonempty set $M\subseteq V(G)$) a vertex $v$ of $G$ is said to be $k$-controlled by $M$ if $\delta_{M}(v) \geq \frac{\delta_{V(G)}(v)}{2}+k$ where $\delta_{M}(v)$ represents the number of neighbors of $v$ in $M$. The set $M$ is alled an open $k$-monopoly for $G$ if it $k$-controls every vertex $v$ of $G$. In this short note we prove that the problem of computing the minimum cardinality of an open k-monopoly in a graph for a negative integer $k$ is NP-complete even restricted to chordal graphs.
Access status: Open Access ,
Wiener index of strong product of graphs
(Wydawnictwa AGH, 2018) Peterin, Iztok; Žigert Pleteršek, Petra
The Wiener index of a connected graph $G$ is the sum of distances between all pairs of vertices of $G$. The strong product is one of the four most investigated graph products. In this paper the general formula for the Wiener index of the strong product of connected graphs is given. The formula can be simplified if both factors are graphs with the constant eccentricity. Consequently, closed formulas for the Wiener index of the strong product of a connected graph $G$ of constant eccentricity with a cycle are derived.