BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mirka Miller

Mirka Miller appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COData Structures and AlgorithmsDiscrete Mathematics

Catalog footprint

What is connected

7works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

7 published item(s)

preprint2016arXiv

A revised Moore bound for mixed graphs

The degree-diameter problem seeks to find the maximum possible order of a graph with a given (maximum) degree and diameter. It is known that graphs attaining the maximum possible value (the Moore bound) are extremely rare, but much activity is focused on finding new examples of graphs or families of graph with orders approaching the bound as closely as possible. There has been recent interest in this problem as it applies to mixed graphs, in which we allow some of the edges to be undirected and some directed. A 2008 paper of Nguyen and Miller derived an upper bound on the possible number of vertices of such graphs. We show that for diameters larger than three, this bound can be reduced and we present a corrected Moore bound for mixed graphs, valid for all diameters and for all combinations of undirected and directed degrees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Partition Dimension of Circulant Graphs

For a vertex $v$ of a connected graph $G(V,E)$ and a subset $S$ of $V$, the distance between $v$ and $S$ is defined by $d(v,S)=min\{d(v,x):x \in S \}.$ For an ordered \emph{k}-partition $Π=\{S_1,S_2\ldots S_k\}$ of $V$, the representation of $v$ with respect to $Π$ is the $k$-vector $r(v|Π) =(d(v,S_1),d(v,S_2)\ldots d(v,S_k)).$ The $k$-partition $Π$ is a resolving partition if the $k$-vectors $r(v|Π)$, $v \in V$ are distinct. The minimum $k$ for which there is a resolving $k$-partition of $V$ is the \emph{partition dimension} of $G$. Salman et al.{\rm\cite{SaJaCh12}} claimed that \emph{partition dimension} of a class of circulant graphs $C(n,\pm \{1,2\})$, for all even $n\geq6$ is 4 and it is 3 when $n$ is odd. In this paper we obtain the partition dimension of circulant graphs $G=C(n, \pm \{1,2 \ldots j\}), 1\leq j < \lfloor \frac{n}{2}\rfloor$, $n \geq(j+k)(j+1)$, $n \equiv \ k \ mod \ (2j)$ and $k$ and $2j$ are co-primes as, \begin{eqnarray*} pd(G) &=& j+1 \ \ \ \ \ \ \ when \ j \ \ is \ even \ and\ all \ k=2m-1, 1 \leq m \leq j \\ pd(G)&=& j+1\ \ \ \ \ \ \ when \ j \ \ is \ odd \ and\ all \ k=2m, 1 \leq m \leq j. \end{eqnarray*}

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Minimum Weight Resolving Sets of Grid Graphs

For a simple graph $G=(V,E)$ and for a pair of vertices $u,v \in V$, we say that a vertex $w \in V$ resolves $u$ and $v$ if the shortest path from $w$ to $u$ is of a different length than the shortest path from $w$ to $v$. A set of vertices ${R \subseteq V}$ is a resolving set if for every pair of vertices $u$ and $v$ in $G$, there exists a vertex $w \in R$ that resolves $u$ and $v$. The minimum weight resolving set problem is to find a resolving set $M$ for a weighted graph $G$ such that$\sum_{v \in M} w(v)$ is minimum, where $w(v)$ is the weight of vertex $v$. In this paper, we explore the possible solutions of this problem for grid graphs $P_n \square P_m$ where $3\leq n \leq m$. We give a complete characterisation of solutions whose cardinalities are 2 or 3, and show that the maximum cardinality of a solution is $2n-2$. We also provide a characterisation of a class of minimals whose cardinalities range from $4$ to $2n-2$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Heuristic for Magic and Antimagic Graph Labellings

Graph labellings have been a very fruitful area of research in the last four decades. However, despite the staggering number of papers published in the field (over 1000), few general results are available, and most papers deal with particular classes of graphs and methods. Here we approach the problem from the computational viewpoint, and in a quite general way. We present the existence problem of a particular labelling as a combinatorial optimization problem, then we discuss the possible strategies to solve it, and finally we present a heuristic for finding different classes of labellings, like vertex-, edge-, or face-magic, and $(a, d)$-antimagic $(v, e, f)$-labellings. The algorithm has been implemented in C++ and MATLAB, and with its aid we have been able to derive new results for some classes of graphs, in particular, vertex-antimagic edge labellings for small graphs of the type $P_2^r \times P_3^s$, for which no general construction is known so far.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On large bipartite graphs of diameter 3

We consider the bipartite version of the {\it degree/diameter problem}, namely, given natural numbers $d\ge2$ and $D\ge2$, find the maximum number $\N^b(d,D)$ of vertices in a bipartite graph of maximum degree $d$ and diameter $D$. In this context, the bipartite Moore bound $\M^b(d,D)$ represents a general upper bound for $\N^b(d,D)$. Bipartite graphs of order $\M^b(d,D)$ are very rare, and determining $\N^b(d,D)$ still remains an open problem for most $(d,D)$ pairs. This paper is a follow-up to our earlier paper \cite{FPV12}, where a study on bipartite $(d,D,-4)$-graphs (that is, bipartite graphs of order $\M^b(d,D)-4$) was carried out. Here we first present some structural properties of bipartite $(d,3,-4)$-graphs, and later prove there are no bipartite $(7,3,-4)$-graphs. This result implies that the known bipartite $(7,3,-6)$-graph is optimal, and therefore $\N^b(7,3)=80$. Our approach also bears a proof of the uniqueness of the known bipartite $(5,3,-4)$-graph, and the non-existence of bipartite $(6,3,-4)$-graphs. In addition, we discover three new largest known bipartite (and also vertex-transitive) graphs of degree 11, diameter 3 and order 190, result which improves by 4 vertices the previous lower bound for $\N^b(11,3)$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Maximum Degree-and-Diameter-Bounded Subgraph in the Mesh

The problem of finding the largest connected subgraph of a given undirected host graph, subject to constraints on the maximum degree $Δ$ and the diameter $D$, was introduced in \cite{maxddbs}, as a generalization of the Degree-Diameter Problem. A case of special interest is when the host graph is a common parallel architecture. Here we discuss the case when the host graph is a $k$-dimensional mesh. We provide some general bounds for the order of the largest subgraph in arbitrary dimension $k$, and for the particular cases of $k=3, Δ= 4$ and $k=2, Δ= 3$, we give constructions that result in sharper lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On graphs of defect at most 2

In this paper we consider the degree/diameter problem, namely, given natural numbers Δ \geq 2 and D \geq 1, find the maximum number N(Δ,D) of vertices in a graph of maximum degree Δ and diameter D. In this context, the Moore bound M(Δ,D) represents an upper bound for N(Δ,D). Graphs of maximum degree Δ, diameter D and order M(Δ,D), called Moore graphs, turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree Δ \geq 2, diameter D \geq 1 and order M(Δ,D) - ε with small ε > 0, that is, (Δ,D,-ε)-graphs. The parameter ε is called the defect. Graphs of defect 1 exist only for Δ = 2. When ε > 1, (Δ,D,-ε)-graphs represent a wide unexplored area. This paper focuses on graphs of defect 2. Building on the approaches developed in [11] we obtain several new important results on this family of graphs. First, we prove that the girth of a (Δ,D,-2)-graph with Δ \geq 4 and D \geq 4 is 2D. Second, and most important, we prove the non-existence of (Δ,D,-2)-graphs with even Δ \geq 4 and D \geq 4; this outcome, together with a proof on the non-existence of (4, 3,-2)-graphs (also provided in the paper), allows us to complete the catalogue of (4,D,-ε)-graphs with D \geq 2 and 0 \leq ε \leq 2. Such a catalogue is only the second census of (Δ,D,-2)-graphs known at present, the first being the one of (3,D,-ε)-graphs with D \geq 2 and 0 \leq ε \leq 2 [14]. Other results of this paper include necessary conditions for the existence of (Δ,D,-2)-graphs with odd Δ \geq 5 and D \geq 4, and the non-existence of (Δ,D,-2)-graphs with odd Δ \geq 5 and D \geq 5 such that Δ \equiv 0, 2 (mod D).

0 citations0 reviewsNo code linkedOpen access