Source author record

Gabor Meszaros

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

5works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Frustrated Triangles

A triple of vertices in a graph is a \emph{frustrated triangle} if it induces an odd number of edges. We study the set $F_n\subset[0,\binom{n}{3}]$ of possible number of frustrated triangles $f(G)$ in a graph $G$ on $n$ vertices. We prove that about two thirds of the numbers in $[0,n^{3/2}]$ cannot appear in $F_n$ , and we characterise the graphs $G$ with $f(G)\in[0,n^{3/2}]$ . More precisely, our main result is that, for each $n\geq 3$ , $F_n$ contains two interlacing sequences $0=a_0\leq b_0\leq a_1\leq b_1\leq \dots \leq a_m\leq b_m\sim n^{3/2}$ such that $F_n\cap(b_t,a_{t+1})=\emptyset$ for all $t$ , where the gaps are $|b_t-a_{t+1}|=(n-2)-t(t+1)$ and $|a_t-b_t|=t(t-1)$ . Moreover, $f(G)\in[a_t,b_t]$ if and only if $G$ can be obtained from a complete bipartite graph by flipping exactly $t$ edges/nonedges. On the other hand, we show, for all $n$ sufficiently large, that if $m\in[f(n),\binom{n}{3}-f(n)]$ , then $m\in F_n$ where $f(n)$ is asymptotically best possible with $f(n)\sim n^{3/2}$ for $n$ even and $f(n)\sim \sqrt{2}n^{3/2}$ for $n$ odd. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with $n$ vertices and $e\leq n^2/4$ edges.

preprint2015arXiv

On Path-Pairability of Cartesian Product of Complete Bipartite Graphs

We study inheritance of path-pairability in the Cartesian product of graphs, and prove different (such as additive and multiplicative) inheritance patterns of path-pairability, depending on the size of the Cartesian product. We present path-pairable graph families, that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.

preprint2015arXiv

Sorting using non-binary comparisons

In this paper we investigate the problem of sorting a set of $n$ coins, each with distinct but unknown weights, using an unusual scale. The classical version of this problem, which has been well-studied, gives the user a binary scale, enabling them to determine which is the lighter/heavier of any two objects. We generalise this, considering a scale that accepts $k$ coins as input and returns the $t^{\text{th}}$ lightest, for a fixed $k$ and $t$ . We consider this in both an on-line and off-line setting, and exhibit algorithms in both settings that are best-possible in terms of the order of the number of queries required.

preprint2014arXiv

Note on the Diameter of Path-Pairable Graphs

A graph on $2k$ vertices is path-pairable if for any pairing of the vertices the pairs can be joined by edge-disjoint paths. The so far known families of path-pairable graphs have diameter of length at most 3. In this paper we present an infinite family of path-pairable graphs with diameter $d(G)=O(\sqrt{n})$ where $n$ denotes the number of vertices of the graph. We prove that our example is extremal up to a constant factor.

preprint2014arXiv

On Linkedness of Cartesian Product of Graphs

We study linkedness of Cartesian product of graphs and prove that the product of an $a$ -linked and a $b$ -linked graphs is $(a+b-1)$ -linked if the graphs are sufficiently large. Further bounds in terms of connectivity are shown. We determine linkedness of product of paths and product of cycles.

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.

Gabor Meszaros

Research overview

Is this your work?

5 publications

Frustrated Triangles

On Path-Pairability of Cartesian Product of Complete Bipartite Graphs

Sorting using non-binary comparisons

Note on the Diameter of Path-Pairable Graphs

On Linkedness of Cartesian Product of Graphs

See the researcher in context

Building this map preview