Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 11

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  hypercube
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

The Path-Distance-Width of Hypercubes

100%
Otachi Y.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
467-470
EN
The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S ⊆ V (G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i. In this note, we determine the path-distance-width of hypercubes.
2
Content available remote

Tietze Extension Theorem for n-dimensional Spaces

100%
Pąk K.
Formalized Mathematics
|
2014
|
tom 22
|
nr 1
11-19
EN
In this article we prove the Tietze extension theorem for an arbitrary convex compact subset of εn with a non-empty interior. This theorem states that, if T is a normal topological space, X is a closed subset of T, and A is a convex compact subset of εn with a non-empty interior, then a continuous function f : X → A can be extended to a continuous function g : T → εn. Additionally we show that a subset A is replaceable by an arbitrary subset of a topological space that is homeomorphic with a convex compact subset of En with a non-empty interior. This article is based on [20]; [23] and [22] can also serve as reference books.
3
Content available remote

Packing the Hypercube

80%
Offner D.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 1
85-93
EN
Let G be a graph that is a subgraph of some n-dimensional hypercube Qn. For sufficiently large n, Stout [20] proved that it is possible to pack vertex- disjoint copies of G in Qn so that any proportion r < 1 of the vertices of Qn are covered by the packing. We prove an analogous theorem for edge-disjoint packings: For sufficiently large n, it is possible to pack edge-disjoint copies of G in Qn so that any proportion r < 1 of the edges of Qn are covered by the packing.
4
Content available remote

Characterizing which Powers of Hypercubes and Folded Hyper- cubes Are Divisor Graphs

80%
AbuHijleh E. A., AbuGhneim O. A., Al-Ezeh H.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
301-311
EN
In this paper, we show that Qkn is a divisor graph, for n = 2, 3. For n ≥ 4, we show that Qkn is a divisor graph iff k ≥ n − 1. For folded-hypercube, we get FQn is a divisor graph when n is odd. But, if n ≥ 4 is even integer, then FQn is not a divisor graph. For n ≥ 5, we show that (FQn)k is not a divisor graph, where 2 ≤ k ≤ [n/2] − 1.
5
Content available remote

Matchings Extend to Hamiltonian Cycles in 5-Cube

80%
Wang F., Zhao W.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
217-231
EN
Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ∈ {2, 3, 4}. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On distinguishing and distinguishing chromatic numbers of hypercubes

80%
Klöckl W.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
419-429
EN
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 results extend work on finite graphs by Bogstad and Cowen on the distinguishing number and Choi, Hartke and Kaul on the distinguishing chromatic number.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the rainbow connection of Cartesian products and their subgraphs

70%
Klavžar S., Mekiš G.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
783-793
EN
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called Θ-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some maximum multigraphs and edge/vertex distance colourings

61%
Skupień Z.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 1
89-106
EN
Shannon-Vizing-type problems concerning the upper bound for a distance chromatic index of multigraphs G in terms of the maximum degree Δ(G) are studied. Conjectures generalizing those related to the strong chromatic index are presented. The chromatic d-index and chromatic d-number of paths, cycles, trees and some hypercubes are determined. Among hypercubes, however, the exact order of their growth is found.
9
Content available remote

Distance Magic Cartesian Products of Graphs

61%
Cichacz S., Froncek D., Krop E., Raridan C.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
299-308
EN
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 vertices to be distance magic.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Embedding complete ternary trees into hypercubes

61%
Choudum S., Lavanya S.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
463-476
EN
We inductively describe an embedding of a complete ternary tree Tₕ of height h into a hypercube Q of dimension at most ⎡(1.6)h⎤+1 with load 1, dilation 2, node congestion 2 and edge congestion 2. This is an improvement over the known embedding of Tₕ into Q. And it is very close to a conjectured embedding of Havel [3] which states that there exists an embedding of Tₕ into its optimal hypercube with load 1 and dilation 2. The optimal hypercube has dimension ⎡(log₂3)h⎤ ( = ⎡(1.585)h⎤) or ⎡(log₂3)h⎤+1.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Parity vertex colouring of graphs

61%
Borowiecki P., Budajová K., Jendrol' S., Krajci S.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
183-195
EN
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.