Opuscula Mathematica
Loading...
ISSN 1232-9274
e-ISSN: 2300-6919
Issue Date
2025
Volume
Vol. 45
Number
No. 1
Description
Journal Volume
Opuscula Mathematica
Vol. 45 (2025)
Projects
Pages
Articles
Graphs with odd and even distances between non-cut vertices
(Wydawnictwa AGH, 2025) Antoshyna,Kateryna; Kozerenko, Sergiy
We prove that in a connected graph, the distances between non-cut vertices are odd if and only if it is the line graph of a strong unique independence tree. We then show that any such tree can be inductively constructed from stars using a simple operation. Further, we study the connected graphs in which the distances between non-cut vertices are even (shortly, NCE-graphs). Our main results on NCE-graphs are the following: we give a criterion of NCE-graphs, show that any bipartite graph is an induced subgraph of an NCE-graph, characterize NCE-graphs with exactly two leaves, characterize graphs that can be subdivided to NCE-graphs, and provide a characterization for NCE-graphs which are maximal with respect to the edge addition operation
Monotonic properties of Kneser solutions of second order linear differential equations with delayed argument
(Wydawnictwa AGH, 2025) Baculíková, Blanka
In this paper new monotonic properties of nonoscillatory solutions for second order linear functional differential equations with delayed argument $\textcolor{white}\$y{''}(t)=p(t)y(\tau(t))\textcolor{white}\$$ have been established. New properties are used to introduce criteria for elimination of bounded nonoscillatory solutions for studied equations.
The metric dimension of circulant graphs
(Wydawnictwa AGH, 2025) Tapendra, BC; Dueck, Shonda
A pair of vertices $x$ and $y$ in a graph $G$ are said to be resolved by a vertex $w$ if the distance from $x$ to $w$ is not equal to the distance from $y$ to $w$. We say that $G$ is resolved by a subset of its vertices $W$ if every pair of vertices in $G$ is resolved by some vertex in $W$. The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$, denoted by $\dim(G)$. The circulant graph $C_n(1,2,\ldots,t)$ is the Cayley graph $ay(\mathbb{Z}_n:\{\pm 1, \pm 2, \ldots, \pm t\})$. In this note we prove that, for $n=2kt+2t$, $\dim(C_n(1,2,\ldots,t))\geq t+2$, confirming Conjecture 4.1.2 in [K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37 (2017), 509-534].
(1,2)-PDS in graphs with the small number of vertices of large degrees
(Wydawnictwa AGH, 2025) Bednarz, Urszula; Pirga, Mateusz
We define and study a perfect $(1,2)$-dominating set which is a special case of a $(1,2)$-dominating set. We discuss the existence of a perfect $(1,2)$-dominating set in graphs with at most two vertices of maximum degree. In particular, we present a complete solution if the maximum degree equals $n-1$ or $n-2$.
Total mutual-visibility in Hamming graphs
(Wydawnictwa AGH, 2025) Bujtás, Csilla; Klavžar, Sandi; Tian, Jing
If $G$ is a graph and $X \subseteq V(G)$, then $X$ is a total mutual-visibility set if every pair of vertices $x$ and $y$ of $G$ admits the shortest $x,y$-path $P$ with $V(P) \cap X \subseteq \{x,y\}$. The cardinality of the largest total mutual-visibility set of $G$ is the total mutual-visibility number $\mu_{\rm t}(G)$ of $G$. In this paper the total mutual-visibility number is studied on Hamming graphs, that is, Cartesian products of complete graphs. Different equivalent formulations for the problem are derived. The values $\mu_{\rm t}(K_{n_1}\square K_{n_2}\square K_{n_3})$ are determined. It is proved that $\mu_{\rm t}(K_{n_1} \square \cdots \square K_{n_r}) = O(N^{r-2})$, where $N = n_1+\cdots + n_r$, and that $\mu_{\rm t}(K_s^{\square r}) = \Theta(s^{r-2})$ for every $r \geq 3$, where $K_s^{\square r}$ denotes the Cartesian product of $r$ copies of $K_s$. The main theorems are also reformulated as Turán-type results on hypergraphs.