Source author record

Gyula Y. Katona

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

ResearcherUnclaimed source record

math.CO math.DS physics.soc-ph

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Optimal pebbling number of the square grid

A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number $π_{opt}$ is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. The optimal pebbling number of the square grid graph $P_n\square P_m$ was investigated in several papers. In this paper, we present a new method using some recent ideas to give a lower bound on $π_{opt}$ . We apply this technique to prove that $π_{opt}(P_n\square P_m)\geq \frac{2}{13}nm$ . Our method also gives a new proof for $π_{opt}(P_n)=π_{opt}(C_n)=\left\lceil\frac{2n}{3}\right\rceil$ .

preprint2018arXiv

Decomposition of a graph into two disjoint odd subgraphs

An odd (resp. even) subgraph in a multigraph is its subgraph in which every vertex has odd (resp. even) degree. We say that a multigraph can be decomposed into two odd subgraphs if its edge set can be partitioned into two sets so that both form odd subgraphs. In this paper we give a necessary and sufficient condition for the decomposability of a multigraph into two odd subgraphs. We also present a polynomial time algorithm for finding such a decomposition or showing its non-existence. We also deal with the case of the decomposability into an even subgraph and an odd subgraph.

preprint2017arXiv

Properties of minimally $t$ -tough graphs

A graph $G$ is minimally $t$ -tough if the toughness of $G$ is $t$ and the deletion of any edge from $G$ decreases the toughness. Kriesell conjectured that for every minimally $1$ -tough graph the minimum degree $δ(G)=2$ . We show that in every minimally $1$ -tough graph $δ(G)\le\frac{n+2}{3}$ . We also prove that every minimally $1$ -tough claw-free graph is a cycle. On the other hand, we show that for every $t \in \mathbb{Q}$ any graph can be embedded as an induced subgraph into a minimally $t$ -tough graph.

preprint2016arXiv

The Optimal Pebbling Number of Staircase Graphs

Let G be a graph with a distribution of pebbles on its vertices. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. The optimal pebbling number of G is the smallest number of pebbles which can placed on the vertices of G such that, for any vertex v of G, there is a sequence of pebbling moves resulting in at least one pebble on v. We determine the optimal pebbling number for several classes of induced subgraphs of the square grid, which we call staircase graphs.

preprint2015arXiv

SIS epidemic propagation on hypergraphs

Mathematical modeling of epidemic propagation on networks is extended to hypergraphs in order to account for both the community structure and the nonlinear dependence of the infection pressure on the number of infected neighbours. The exact master equations of the propagation process are derived for an arbitrary hypergraph given by its incidence matrix. Based on these, moment closure approximation and mean-field models are introduced and compared to individual-based stochastic simulations. The simulation algorithm, developed for networks, is extended to hypergraphs. The effects of hypergraph structure and the model parameters are investigated via individual-based simulation results.

preprint2010arXiv

Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs

A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices $v$ and $w$ adjacent to a vertex $u$ , and an extra pebble is added at vertex $u$ . A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number is the smallest number $m$ needed to guarantee that any vertex is reachable from any pebble distribution of $m$ pebbles. The optimal rubbling number is the smallest number $m$ needed to guarantee a pebble distribution of $m$ pebbles from which any vertex is reachable. We give bounds for rubbling and optimal rubbling numbers. In particular, we find an upper bound for the rubbling number of $n$ -vertex, diameter $d$ graphs, and estimates for the maximum rubbling number of diameter 2 graphs. We also give a sharp upper bound for the optimal rubbling number, and sharp upper and lower bounds in terms of the diameter.

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.

Gyula Y. Katona

Research overview

Is this your work?

6 publications

Optimal pebbling number of the square grid

Decomposition of a graph into two disjoint odd subgraphs

Properties of minimally $t$ -tough graphs

The Optimal Pebbling Number of Staircase Graphs

SIS epidemic propagation on hypergraphs

Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs

See the researcher in context

Building this map preview

Gyula Y. Katona

Research overview

Is this your work?

6 publications

Optimal pebbling number of the square grid

Decomposition of a graph into two disjoint odd subgraphs

Properties of minimally ttt-tough graphs

The Optimal Pebbling Number of Staircase Graphs

SIS epidemic propagation on hypergraphs

Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs

See the researcher in context

Building this map preview

Properties of minimally $t$ -tough graphs