Source author record

Anita Pasotti

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

12works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Non-zero sum Heffter arrays and their applications

In this paper we introduce a new class of partially filled arrays that, as Heffter arrays, are related to difference families, graph decompositions and biembeddings. A non-zero sum Heffter array $\mathrm{N}\mathrm{H}(m,n; h,k)$ is an $m \times n$ p. f. array with entries in $\mathbb{Z}_{2nk+1}$ such that: each row contains $h$ filled cells and each column contains $k$ filled cells; for every $x\in \mathbb{Z}_{2nk+1}\setminus\{0\}$ , either $x$ or $-x$ appears in the array; the sum of the elements in every row and column is different from $0$ (in $\mathbb{Z}_{2nk+1}$ ). Here first we explain the connections with relative difference families and with path decompositions of the complete multipartite graph. Then we present a complete solution for the existence problem and a constructive complete solution for the square case and for the rectangular case with no empty cells when the additional, very restrictive, property of "globally simple" is required. Finally, we show how these arrays can be used to construct biembeddings of complete graphs.

preprint2022arXiv

On the number of non-isomorphic (simple) $k$ -gonal biembeddings of complete multipartite graphs

This article aims to provide exponential lower bounds on the number of non-isomorphic $k$ -gonal biembeddings of the complete multipartite graph into orientable surfaces. For this purpose, we use the concept, introduced by Archdeacon in 2015, of Heffer array and its relations with graph embeddings. In particular we show that, under certain hypotheses, from a single Heffter array, we can obtain an exponential number of distinct graph embeddings. Exploiting this idea starting from the arrays constructed by Cavenagh, Donovan and Yazici in 2020, we obtain that, for infinitely many values of $k$ and $v$ , there are at least $k^{\frac{k}{2}+o(k)} \cdot 2^{v\cdot \frac{H(1/4)}{(2k)^2}+o(v)}$ non-isomorphic $k$ -gonal biembeddings of $K_v$ , where $H(\cdot)$ is the binary entropy. Moreover about the embeddings of $K_{\frac{v}{t}\times t}$ , for $t\in\{1,2,k\}$ , we provide a construction of $2^{v\cdot \frac{H(1/4)}{2k(k-1)}+o(v,k)}$ non-isomorphic $k$ -gonal biembeddings whenever $k$ is odd and $v$ belongs to a wide infinite family of values.

preprint2022arXiv

Tight globally simple non-zero sum Heffter arrays and biembeddings

Square relative non-zero sum Heffter arrays, denoted by $\mathrm{N}\mathrm{H}_t(n;k)$ , have been introduced as a variant of the classical concept of Heffter array. An $\mathrm{N}\mathrm{H}_t(n; k)$ is an $n\times n$ partially filled array with elements in $\mathbb{Z}_v$ , where $v=2nk+t$ , whose rows and whose columns contain $k$ filled cells, such that the sum of the elements in every row and column is different from $0$ (modulo $v$ ) and, for every $x\in \mathbb{Z}_v$ not belonging to the subgroup of order $t$ , either $x$ or $-x$ appears in the array. In this paper we give direct constructions of square non-zero sum Heffter arrays with no empty cells, $\mathrm{N}\mathrm{H}_t(n;n)$ , for every $n$ odd, when $t$ is a divisor of $n$ and when $t\in\{2,2n,n^2,2n^2\}$ . The constructed arrays have also the very restrictive property of being "globally simple"; this allows us to get new orthogonal path decompositions and new biembeddings of complete multipartite graphs.

preprint2020arXiv

Relative Heffter arrays and biembeddings

Relative Heffter arrays, denoted by $\mathrm{H}_t(m,n; s,k)$ , have been introduced as a generalization of the classical concept of Heffter array. A $\mathrm{H}_t(m,n; s,k)$ is an $m\times n$ partially filled array with elements in $\mathbb{Z}_v$ , where $v=2nk+t$ , whose rows contain $s$ filled cells and whose columns contain $k$ filled cells, such that the elements in every row and column sum to zero and, for every $x\in \mathbb{Z}_v$ not belonging to the subgroup of order $t$ , either $x$ or $-x$ appears in the array. In this paper we show how relative Heffter arrays can be used to construct biembeddings of cyclic cycle decompositions of the complete multipartite graph $K_{\frac{2nk+t}{t}\times t}$ into an orientable surface. In particular, we construct such biembeddings providing integer globally simple square relative Heffter arrays for $t=k=3,5,7,9$ and $n\equiv 3 \pmod 4$ and for $k=3$ with $t=n,2n$ , any odd $n$ .

preprint2016arXiv

Cyclic uniform 2-factorizations of the complete multipartite graph

The generalization of the Oberwolfach Problem, proposed by J. Liu in 2000, asks for a uniform $2$ -factorization of the complete multipartite graph $K_{m\times n}$ . Here we focus our attention on $2$ -factorizations regular under the cyclic group $Z_{mn}$ , whose $2$ -factors are disjoint union of cycles all of even length $\ell$ . In particular, we present a complete solution for the extremal cases $\ell=4$ and $\ell=mn$ .

preprint2015arXiv

A generalization of the problem of Mariusz Meszka

Mariusz Meszka has conjectured that given a prime p=2n+1 and a list L containing n positive integers not exceeding n there exists a near 1-factor in K_p whose list of edge-lengths is L. In this paper we propose a generalization of this problem to the case in which p is an odd integer not necessarily prime. In particular, we give a necessary condition for the existence of such a near 1-factor for any odd integer p. We show that this condition is also sufficient for any list L whose underlying set S has size 1, 2, or n. Then we prove that the conjecture is true if S={1,2,t} for any positive integer t not coprime with the order p of the complete graph. Also, we give partial results when t and p are coprime. Finally, we present a complete solution for t<12.

preprint2015arXiv

Cyclic hamiltonian cycle systems of the complete multipartite graph: even number of parts

A hamiltonian cycle system (HCS, for short) of a graph $Γ$ is a partition of the edges of $Γ$ into hamiltonian cycles. A HCS is cyclic when it is invariant under a cyclic permutation of all the vertices of $Γ$ ; the existence problem for a cyclic HCS has been completely solved by Buratti and Del Fra in 2004 when $Γ$ is the complete graph $K_v$ , $v$ odd, and by Jordon and Morris in 2008 when $Γ$ is the complete graph minus a $1$ -factor $K_v-I$ , $v$ even. In this work we present a complete solution to the existence problem of a cyclic HCS for $Γ= K_{m\times n}$ , the complete multipartite graph, when the number of parts $m$ is even. We also give necessary and sufficient conditions for the existence of a cyclic and symmetric HCS of $Γ$ ; the notion of a symmetric HCS of a graph $Γ$ has been introduced in 2004 by Akiyama, Kobayashi, and Nakamura for $Γ=K_v$ , $v$ odd, in 2011 by Brualdi and Schroeder when $Γ= K_v-I$ , $v$ even, and, very recently, by Schroeder when $Γ$ is the complete multipartite graph.

preprint2014arXiv

On the Buratti-Horak-Rosa Conjecture about Hamiltonian Paths in Complete Graphs

In this paper we investigate a problem proposed by Marco Buratti, Peter Horak and Alex Rosa (denoted by BHR-problem) concerning Hamiltonian paths in the complete graph with prescribed edge-lengths. In particular we solve BHR({1^a,2^b,t^c}) for any even integer t>=4, provided that a+b>=t-1. Furthermore, for t=4,6,8 we present a complete solution of BHR({1^a,2^b,t^c}) for any positive integer a,b,c.

preprint2013arXiv

A new result on the problem of Buratti, Horak and Rosa

The conjecture of Peter Horak and Alex Rosa (generalizing that of Marco Buratti) states that a multiset L of v-1 positive integers not exceeding [v/2] is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set {0,1,...,v-1} if and only if the following condition (here reformulated in a slightly easier form) is satisfied: for every divisor d of v, the number of multiples of d appearing in L is at most v-d. In this paper we do some preliminary discussions on the conjecture, including its relationship with graph decompositions. Then we prove, as main result, that the conjecture is true whenever all the elements of L are in {1,2,3,5}.

preprint2011arXiv

Down-linking $(K_v,Γ)$ -designs to $P_3$ -designs

Let G' be a subgraph of a graph G. We define a down-link from a (K_v,G)-design B to a (K_n,G')-design B' as a map f:B->B' mapping any block of B into one of its subgraphs. This is a new concept, closely related with both the notion of metamorphosis and that of embedding. In the present paper we study down-links in general and prove that any (K_v,G)-design might be down-linked to a (K_n,G')-design, provided that n is admissible and large enough. We also show that if G'=P_3, it is always possible to find a down-link to a design of order at most v+3. This bound is then improved for several classes of graphs Gamma, by providing explicit constructions.

preprint2011arXiv

New results on path-decompositions and their down-links

In (arXiv:1004.4127) the concept of down-link from a (K_v, G)-design B to a (K_n, G')-design B' has been introduced. In the present paper the spectrum problems for G'= P4 are studied. General results on the existence of path-decompositions and embeddings between path- decompositions playing a fundamental role for the construction of down-links are also presented

preprint2011arXiv

On $d$ -divisible graceful $α$ -labelings of $C_{4k}\times P_m$

In a previous paper the concept of a $d$ -divisible graceful $α$ -labeling has been introduced as a generalization of classical $α$ -labelings and it has been shown how it is useful to obtain certain cyclic graph decompositions. In the present paper it is proved the existence of $d$ -divisible graceful $α$ -labelings of $C_{4k}\times P_m$ for any integers $k\geq1$ , $m\geq2$ for several values of $d$ .

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.

Anita Pasotti

Research overview

Is this your work?

12 publications

Non-zero sum Heffter arrays and their applications

On the number of non-isomorphic (simple) $k$ -gonal biembeddings of complete multipartite graphs

Tight globally simple non-zero sum Heffter arrays and biembeddings

Relative Heffter arrays and biembeddings

Cyclic uniform 2-factorizations of the complete multipartite graph

A generalization of the problem of Mariusz Meszka

Cyclic hamiltonian cycle systems of the complete multipartite graph: even number of parts

On the Buratti-Horak-Rosa Conjecture about Hamiltonian Paths in Complete Graphs

A new result on the problem of Buratti, Horak and Rosa

Down-linking $(K_v,Γ)$ -designs to $P_3$ -designs

New results on path-decompositions and their down-links

On $d$ -divisible graceful $α$ -labelings of $C_{4k}\times P_m$

See the researcher in context

Building this map preview

Anita Pasotti

Research overview

Is this your work?

12 publications

Non-zero sum Heffter arrays and their applications

On the number of non-isomorphic (simple) kkk-gonal biembeddings of complete multipartite graphs

Tight globally simple non-zero sum Heffter arrays and biembeddings

Relative Heffter arrays and biembeddings

Cyclic uniform 2-factorizations of the complete multipartite graph

A generalization of the problem of Mariusz Meszka

Cyclic hamiltonian cycle systems of the complete multipartite graph: even number of parts

On the Buratti-Horak-Rosa Conjecture about Hamiltonian Paths in Complete Graphs

A new result on the problem of Buratti, Horak and Rosa

Down-linking (Kv,Γ)(K_v,Γ)(Kv​,Γ)-designs to P3P_3P3​-designs

New results on path-decompositions and their down-links

On ddd-divisible graceful ααα-labelings of C4k×PmC_{4k}\times P_mC4k​×Pm​

See the researcher in context

Building this map preview

On the number of non-isomorphic (simple) $k$ -gonal biembeddings of complete multipartite graphs

Down-linking $(K_v,Γ)$ -designs to $P_3$ -designs

On $d$ -divisible graceful $α$ -labelings of $C_{4k}\times P_m$