Source author record

Tanja Gologranc

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Daisy Hamming graphs

Daisy graphs of a rooted graph $G$ with the root $r$ were recently introduced as a generalization of daisy cubes, a class of isometric subgraphs of hypercubes. In this paper we first solve the problem posed in \cite{Taranenko2020} and characterize rooted graphs $G$ with the root $r$ for which all daisy graphs of $G$ with respect to $r$ are isometric in $G$ . We continue the investigation of daisy graphs $G$ (generated by $X$ ) of a Hamming graph $H$ and characterize those daisy graphs generated by $X$ of cardinality 2 that are isometric in $H$ . Finally, we give a characterization of isometric daisy graphs of a Hamming graph $K_{k_1}\Box \ldots \Box K_{k_n}$ with respect to $0^n$ in terms of an expansion procedure.

preprint2016arXiv

Dominating sequences in grid-like and toroidal graphs

A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$ . In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.

preprint2016arXiv

Dominating sequences under atomic changes with applications in Sierpiński and interval graphs

A sequence $S=(v_1,\ldots,v_k)$ of distinct vertices of a graph $G$ is called a legal sequence if $N[v_i] \setminus \cup_{j=1}^{i-1}N[v_j]\not=\emptyset$ for any $i$ . The maximum length of a legal (dominating) sequence in $G$ is called the Grundy domination number $γ_{gr}(G)$ of a graph $G$ . It is known that the problem of determining the Grundy domination number is NP-complete in general, while efficient algorithm exist for trees and some other classes of graphs. In this paper we find an efficient algorithm for the Grundy domination number of an interval graph. We also show the exact value of the Grundy domination number of an arbitrary Sierpiński graph $S_p^n$ , and present algorithms to construct the corresponding sequence. These results are obtained by using the main result of the paper, which are sharp bounds for the Grundy domination number of a vertex- and edge-removed graph. That is, given a graph $G$ , $e\in E(G)$ , and $u\in V(G)$ , we prove that $γ_{gr}(G)-1\le γ_{gr}(G-e) \le γ_{gr}(G)+1$ and $γ_{gr}(G)-2\le γ_{gr}(G-u) \le γ_{gr}(G)$ . For each of the bounds there exist graphs, in which all three possibilities occur for different edges, respectively vertices.

preprint2016arXiv

Toll number of the Cartesian and the lexicographic product of graphs

Toll convexity is a variation of the so-called interval convexity. A tolled walk $T$ between $u$ and $v$ in $G$ is a walk of the form $T: u,w_1,\ldots,w_k,v,$ where $k\ge 1$ , in which $w_1$ is the only neighbor of $u$ in $T$ and $w_k$ is the only neighbor of $v$ in $T$ . As in geodesic or monophonic convexity, toll interval between $u,v\in V(G)$ is a set $T_G(u,v)=\{x\in V(G)\,:\,x \textrm{ lies on a tolled walk between } u \textrm{ and } v\}$ . A set of vertices $S$ is toll convex, if $T_{G}(u,v)\subseteq S$ for all $u,v\in S$ . First part of the paper reinvestigates the characterization of convex sets in the Cartesian product of graphs. Toll number and toll hull number of the Cartesian product of two arbitrary graphs is proven to be 2. The second part deals with the lexicographic product of graphs. It is shown that if $H$ is not isomorphic to a complete graph, $tn(G \circ H) \leq 3\cdot tn(G)$ . We give some necessary and sufficient conditions for $tn(G \circ H) = 3\cdot tn(G)$ . Moreover, if $G$ has at least two extreme vertices, a complete characterization is given. Also graphs with $tn(G \circ H)=2$ are characterized - this is the case iff $G$ has an universal vertex and $tn(H)=2$ . Finally, the formula for $tn(G \circ H)$ is given - it is described in terms of the so-called toll-dominating triples.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Tanja Gologranc

Research overview

Is this your work?

4 publications

Daisy Hamming graphs

Dominating sequences in grid-like and toroidal graphs

Dominating sequences under atomic changes with applications in Sierpiński and interval graphs

Toll number of the Cartesian and the lexicographic product of graphs

See the researcher in context

Building this map preview