Currently displaying 1 – 15 of 15

Showing per page

Order by Relevance | Title | Year of publication

2-halvable complete 4-partite graphs

Dalibor Fronček — 1998

Discussiones Mathematicae Graph Theory

A complete 4-partite graph K m ₁ , m ₂ , m ₃ , m ₄ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs K m ₁ , m ₂ , m ₃ , m ₄ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs K m ₁ , m ₂ , m ₃ , m ₄ with four odd parts (i.e., the graphs K m , m , m , n and K m , m , n , n ) all d-halvable graphs are known as well, except for the graphs K m , m , n , n when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs K m ₁ , m ₂ , m ₃ , m ₄ with three or four different...

Note on cyclic decompositions of complete bipartite graphs into cubes

Dalibor Fronček — 1999

Discussiones Mathematicae Graph Theory

So far, the smallest complete bipartite graph which was known to have a cyclic decomposition into cubes Q d of a given dimension d was K d 2 d - 1 , d 2 d - 2 . We improve this result and show that also K d 2 d - 2 , d 2 d - 2 allows a cyclic decomposition into Q d . We also present a cyclic factorization of K 8 , 8 into Q₄.

Cyclic decompositions of complete graphs into spanning trees

Dalibor Froncek — 2004

Discussiones Mathematicae Graph Theory

We examine decompositions of complete graphs with an even number of vertices, K 2 n , into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.

Product rosy labeling of graphs

Dalibor Fronček — 2008

Discussiones Mathematicae Graph Theory

In this paper we describe a natural extension of the well-known ρ-labeling of graphs (also known as rosy labeling). The labeling, called product rosy labeling, labels vertices with elements of products of additive groups. We illustrate the usefulness of this labeling by presenting a recursive construction of infinite families of trees decomposing complete graphs.

Decomposition of Certain Complete Bipartite Graphs into Prisms

Dalibor Froncek — 2017

Discussiones Mathematicae Graph Theory

Häggkvist [6] proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K6n,6n. In [1] Cichacz and Froncek established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph Kn,n into generalized prisms of order 2n. In [2] and [3] Cichacz, Froncek, and Kovar showed decompositions of K3n/2,3n/2 into generalized prisms of order 2n. In this paper we prove that K6n/5,6n/5...

Rectangular table negotiation problem revisited

Dalibor Froncek;  Michael Kubesa — 2011

Open Mathematics

We solve the last missing case of a “two delegation negotiation” version of the Oberwolfach problem, which can be stated as follows. Suppose we have two negotiating delegations with n=mk members each and we have a seating arrangement such that every day the negotiators sit at m tables with k people of the same delegation at one side of each table. Every person can effectively communicate just with three nearest persons across the table. Our goal is to guarantee that over the course of several days,...

Orthogonal double covers of complete graphs by fat caterpillars

Dalibor Froncek;  Uwe Leck — 2006

Discussiones Mathematicae Graph Theory

An orthogonal double cover (ODC) of the complete graph Kₙ by some graph G is a collection of n spanning subgraphs of Kₙ, all isomorphic to G, such that any two of the subgraphs share exactly one edge and every edge of Kₙ is contained in exactly two of the subgraphs. A necessary condition for such an ODC to exist is that G has exactly n-1 edges. We show that for any given positive integer d, almost all caterpillars of diameter d admit an ODC of the corresponding complete graph.

On traceability and 2-factors in claw-free graphs

Dalibor Fronček;  Zdeněk Ryjáček;  Zdzisław Skupień — 2004

Discussiones Mathematicae Graph Theory

If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to ⋃ ⁸ i = 1 i or is traceable.

Decomposition of complete graphs into ( 0 , 2 ) -prisms

Sylwia Cichacz;  Soleh Dib;  Dalibor Fronček — 2014

Czechoslovak Mathematical Journal

R. Frucht and J. Gallian (1988) proved that bipartite prisms of order 2 n have an α -labeling, thus they decompose the complete graph K 6 n x + 1 for any positive integer x . We use a technique called the ρ + -labeling introduced by S. I. El-Zanati, C. Vanden Eynden, and N. Punnim (2001) to show that also some other families of 3-regular bipartite graphs of order 2 n called generalized prisms decompose the complete graph K 6 n x + 1 for any positive integer x .

Distance Magic Cartesian Products of Graphs

Sylwia Cichacz;  Dalibor Froncek;  Elliot Krop;  Christopher Raridan — 2016

Discussiones Mathematicae Graph Theory

A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ : V → {1, . . . , n} such that the weight of every vertex v, computed as the sum of the labels on the vertices in the open neighborhood of v, is a constant. In this paper, we show that hypercubes with dimension divisible by four are not distance magic. We also provide some positive results by proving necessary and sufficient conditions for the Cartesian product of certain complete multipartite graphs and the cycle on four...

Page 1

Download Results (CSV)