Source author record

Andrej Taranenko

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

3works

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

Mixed metric dimension of graphs

Let $G=(V,E)$ be a connected graph. A vertex $w\in V$ distinguishes two elements (vertices or edges) $x,y\in E\cup V$ if $d_G(w,x)\ne d_G(w,y)$ . A set $S$ of vertices in a connected graph $G$ is a mixed metric generator for $G$ if every two elements (vertices or edges) of $G$ are distinguished by some vertex of $S$ . The smallest cardinality of a mixed metric generator for $G$ is called the mixed metric dimension and is denoted by $\mathrm{mdim}(G)$ . In this paper we consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. We also give results about the mixed metric dimension of some families of graphs and present an upper bound with respect to the girth of a graph. Finally, we prove that the problem of determining the mixed metric dimension of a graph is NP-hard in the general case.

preprint2014arXiv

A note on the Thue chromatic number of lexicographic products of graphs

A sequence is called non-repetitive if no of its subsequences forms a repetition (a sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$ ). Let $G$ be a graph whose vertices are coloured. A colouring $φ$ of the graph $G$ is non-repetitive if the sequence of colours on every path in $G$ is non-repetitive. The Thue chromatic number, denoted by $π(G)$ , is the minimum number of colours of a non-repetitive colouring of $G$ . In this short note we present a general upper bound for the Thue chromatic number for the lexicographic product $G\circ H$ of graphs $G$ and $H$ with respect to some properties of the factors. This upper bound is then used to derive the exact values for $π(G\circ H)$ when $G$ is a complete multipartite graph and $H$ is an arbitrary graph.

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.