Researcher profile

Andrej Taranenko

Andrej Taranenko contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.CO

Trust snapshot

Quick read

Trust 15 - Baseline

3works

0followers

1topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

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.