Note on cyclic decompositions of complete bipartite graphs into cubes

Dalibor Fronček

Displaying similar documents to “Note on cyclic decompositions of complete bipartite graphs into cubes”

A note on another construction of graphs with $4 n + 6$ vertices and cyclic automorphism group of order $4 n$

Peteris Daugulis (2017)

Archivum Mathematicum

Similarity:

The problem of finding minimal vertex number of graphs with a given automorphism group is addressed in this article for the case of cyclic groups. This problem was considered earlier by other authors. We give a construction of an undirected graph having $4 n + 6$ vertices and automorphism group cyclic of order $4 n$ , $n \geq 1$ . As a special case we get graphs with $2^{k} + 6$ vertices and cyclic automorphism groups of order $2^{k}$ . It can revive interest in related problems.

Kannan-type cyclic contraction results in $2$ -Menger space

Binayak S. Choudhury, Samir Kumar BHANDARI (2016)

Mathematica Bohemica

Similarity:

In this paper we establish Kannan-type cyclic contraction results in probabilistic 2-metric spaces. We use two different types of $t$ -norm in our theorems. In our first theorem we use a Hadzic-type $t$ -norm. We use the minimum $t$ -norm in our second theorem. We prove our second theorem by different arguments than the first theorem. A control function is used in our second theorem. These results generalize some existing results in probabilistic 2-metric spaces. Our results are illustrated with...

Cyclic Type Fixed Point Results in 2-Menger Spaces

Binayak S. CHOUDHURY, Samir Kumar BHANDARI, Parbati SAHA (2015)

Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica

Similarity:

In this paper we introduce generalized cyclic contractions through $r$ number of subsets of a probabilistic 2-metric space and establish two fixed point results for such contractions. In our first theorem we use the Hadzic type $t$ -norm. In another theorem we use a control function with minimum $t$ -norm. Our results generalizes some existing fixed point theorem in 2-Menger spaces. The results are supported with some examples.

On the Rockafellar theorem for $Φ^{γ (\cdot, \cdot)}$ -monotone multifunctions

S. Rolewicz (2006)

Studia Mathematica

Similarity:

Let X be an arbitrary set, and γ: X × X → ℝ any function. Let Φ be a family of real-valued functions defined on X. Let $Γ : X \to 2^{Φ}$ be a cyclic $Φ^{γ (\cdot, \cdot)}$ -monotone multifunction with non-empty values. It is shown that the following generalization of the Rockafellar theorem holds. There is a function f: X → ℝ such that Γ is contained in the $Φ^{γ (\cdot, \cdot)}$ -subdifferential of f, $Γ (x) \subset \partial_{Φ}^{γ (\cdot, \cdot)} {f |}_{x}$ .

Moufang loops of order coprime to three that cyclically extend groups of dihedral type

Aleš Drápal (2016)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

This paper completely solves the isomorphism problem for Moufang loops $Q = G C$ where $G ⊴ Q$ is a noncommutative group with cyclic subgroup of index two and $| Z (G) | \leq 2$ , $C$ is cyclic, $G \cap C = 1$ , and $Q$ is finite of order coprime to three.

Remarks on $D$ -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or $D$ -integral) if all eigenvalues of its distance matrix are integers. In their study of $D$ -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$ -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_{1}, p_{2}, p_{3}}$ with $p_{1} < p_{2} < p_{3}$ , and $K_{p_{1}, p_{2}, p_{3}, p_{4}}$ with $p_{1} < p_{2} < p_{3} < p_{4}$ , as well as the infinite classes of distance integral...

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g (n, l)$ , the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$ . By edit distance of two graphs $G$ , $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$ . This new extremal number $g (n, l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

Intrinsic linking and knotting are arbitrarily complex

Erica Flapan, Blake Mellor, Ramin Naimi (2008)

Fundamenta Mathematicae

Similarity:

We show that, given any n and α, any embedding of any sufficiently large complete graph in ℝ³ contains an oriented link with components Q₁, ..., Qₙ such that for every i ≠ j, $| l k (Q_{i}, Q_{j}) | \geq α$ and $| a ₂ (Q_{i}) | \geq α$ , where $a ₂ (Q_{i})$ denotes the second coefficient of the Conway polynomial of $Q_{i}$ .

Edge-colouring of graphs and hereditary graph properties

Samantha Dorfling, Tomáš Vetrík (2016)

Czechoslovak Mathematical Journal

Similarity:

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph $G$ , a hereditary graph property $𝒫$ and $l \geq 1$ we define $χ_{𝒫, l}^{'} (G)$ to be the minimum number of colours needed to properly colour the edges of $G$ , such that any subgraph of $G$ induced by edges coloured by (at most) $l$ colours is in $𝒫$ . We present a necessary and sufficient condition for the existence of $χ_{𝒫, l}^{'} (G)$ . We focus on edge-colourings of graphs with respect to the hereditary...

On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number $χ_{D} (G)$ of G. Extending these concepts to infinite graphs we prove that $D (Q_{ℵ} ₀) = 2$ and $χ_{D} (Q_{ℵ} ₀) = 3$ , where $Q_{ℵ} ₀$ denotes the hypercube of countable dimension. We also show that $χ_{D} (Q ₄) = 4$ , thereby completing the investigation of finite hypercubes with respect to $χ_{D}$ . Our...

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let $α_{} (G)$ and $α *_{} (G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on $α_{} (G)$ and $α *_{} (G)$ are presented.

Realizable Galois module classes over the group ring for non abelian extensions

Nigel P. Byott, Bouchaïb Sodaïgui (2013)

Annales de l’institut Fourier

Similarity:

Given an algebraic number field $k$ and a finite group $Γ$ , we write $ℛ (O_{k} [Γ])$ for the subset of the locally free classgroup $Cl (O_{k} [Γ])$ consisting of the classes of rings of integers $O_{N}$ in tame Galois extensions $N / k$ with $Gal (N / k) ≅ Γ$ . We determine $ℛ (O_{k} [Γ])$ , and show it is a subgroup of $Cl (O_{k} [Γ])$ by means of a description using a Stickelberger ideal and properties of some cyclic codes, when $k$ contains a root of unity of prime order $p$ and $Γ = V ⋊ C$ , where $V$ is an elementary abelian group of order $p^{r}$ and $C$ is a cyclic group of order $m > 1$ acting faithfully...

Persistency in the Traveling Salesman Problem on Halin graphs

Vladimír Lacko (2000)

Discussiones Mathematicae Graph Theory

Similarity:

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{A l l}$ , $E_{S o m e}$ , $E_{N o n e}$ of the edge set E, where: $E_{A l l}$ = e ∈ E, e belongs to all optimum solutions, $E_{N o n e}$ = e ∈ E, e does not belong to any optimum solution and $E_{S o m e}$ = e ∈ E, e belongs to some but not to all optimum solutions.

A note on the independent domination number versus the domination number in bipartite graphs

Shaohui Wang, Bing Wei (2017)

Czechoslovak Mathematical Journal

Similarity:

Let $γ (G)$ and $i (G)$ be the domination number and the independent domination number of $G$ , respectively. Rad and Volkmann posted a conjecture that $i (G) / γ (G) \leq Δ (G) / 2$ for any graph $G$ , where $Δ (G)$ is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than $Δ (G) / 2$ are provided as well.

Embedding products of graphs into Euclidean spaces

Mikhail Skopenkov (2003)

Fundamenta Mathematicae

Similarity:

For any collection of graphs $G ₁, . . ., G_{N}$ we find the minimal dimension d such that the product $G ₁ \times . . . \times G_{N}$ is embeddable into $ℝ^{d}$ (see Theorem 1 below). In particular, we prove that (K₅)ⁿ and $(K_{3, 3}) ⁿ$ are not embeddable into $ℝ^{2 n}$ , where K₅ and $K_{3, 3}$ are the Kuratowski graphs. This is a solution of a problem of Menger from 1929. The idea of the proof is a reduction to a problem from so-called Ramsey link theory: we show that any embedding $L k O \to S^{2 n - 1}$ , where O is a vertex of (K₅)ⁿ, has a pair of linked (n-1)-spheres.