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: 9

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  Cartesian product of graphs
help Sortuj według:

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

On Path-Pairability in the Cartesian Product of Graphs

100%
Mészáros G.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
743-758
EN
We study the inheritance of path-pairability in the Cartesian product of graphs and prove additive and multiplicative inheritance patterns of path-pairability, depending on the number of vertices in the Cartesian product. We present path-pairable graph families that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.
2
Content available remote

Motion planning in cartesian product graphs

100%
Deb B., Kapoor K.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
207-221
EN
Let G be an undirected graph with n vertices. Assume that a robot is placed on a vertex and n − 2 obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path between the source and destination vertices in graph G. In this article we show that the path traced by the robot coincides with a shortest path in case of Cartesian product graphs. We give the minimum number of moves required for the motion planning problem in Cartesian product of two graphs having girth 6 or more. A result that we prove in the context of Cartesian product of Pn with itself has been used earlier to develop an approximation algorithm for (n2 − 1)-puzzle
3
Content available remote

Edge-Transitive Lexicographic and Cartesian Products

80%
Imrich W., Iranmanesh A., Klavžar S., Soltani A.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
857-865
EN
In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao [11]. For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Note on the split domination number of the Cartesian product of paths

80%
Zwierzchowski M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
79-84
EN
In this note the split domination number of the Cartesian product of two paths is considered. Our results are related to [2] where the domination number of Pₘ ☐ Pₙ was studied. The split domination number of P₂ ☐ Pₙ is calculated, and we give good estimates for the split domination number of Pₘ ☐ Pₙ expressed in terms of its domination number.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On θ-graphs of partial cubes

70%
Klavžar S., Kovse M.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
313-321
EN
The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.
6
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.
7
Content available remote

Rank numbers for bent ladders

61%
Richter P., Leven E., Tran A., Ek B., Jacob J., Narayan D. A.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
309-329
EN
A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices with the same label contains a vertex with a larger label. The rank number of a graph is the fewest number of labels that can be used in a ranking. The rank number of a graph is known for many families, including the ladder graph P2 × Pn. We consider how ”bending” a ladder affects the rank number. We prove that in certain cases the rank number does not change, and in others the rank number differs by only 1. We investigate the rank number of a ladder with an arbitrary number of bends
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Minimal rankings of the Cartesian product Kₙ ☐ Kₘ

61%
Eyabi G., Jacob J., Laskar R., Narayan D., Pillone D.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
725-735
EN
For a graph G = (V, E), a function f:V(G) → {1,2, ...,k} is a k-ranking if f(u) = f(v) implies that every u - v path contains a vertex w such that f(w) > f(u). A k-ranking is minimal if decreasing any label violates the definition of ranking. The arank number, $ψ_r(G)$, of G is the maximum value of k such that G has a minimal k-ranking. We completely determine the arank number of the Cartesian product Kₙ ☐ Kₙ, and we investigate the arank number of Kₙ ☐ Kₘ where n > m.
9
Content available remote

How Long Can One Bluff in the Domination Game?

51%
Brešar B., Dorbec P., Klavžar S., Košmrlj G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
337-352
EN
The domination game is played on an arbitrary graph G by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs K(n, 2), n ≥ 6, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.
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ć.