Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "Cartesian product of graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-12 z 12
    Tytuł:
    On Path-Pairability in the Cartesian Product of Graphs
    Autorzy:
    Mészáros, Gábor
    Powiązania:
    https://bibliotekanauki.pl/articles/31340793.pdf
    Data publikacji:
    2016-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    path-pairable graphs
    Cartesian product of graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 3; 743-758
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Note on the split domination number of the Cartesian product of paths
    Autorzy:
    Zwierzchowski, Maciej
    Powiązania:
    https://bibliotekanauki.pl/articles/744304.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination number
    split domination number
    Cartesian product of graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 79-84
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Motion planning in Cartesian product graphs
    Autorzy:
    Deb, Biswajit
    Kapoor, Kalpesh
    Powiązania:
    https://bibliotekanauki.pl/articles/30148104.pdf
    Data publikacji:
    2014-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    robot motion in a graph
    Cartesian product of graphs
    Opis:
    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 $P_n$ with itself has been used earlier to develop an approximation algorithm for ($n^2 − 1$)-puzzle
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 2; 207-221
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Edge-Transitive Lexicographic and Cartesian Products
    Autorzy:
    Imrich, Wilfried
    Iranmanesh, Ali
    Klavžar, Sandi
    Soltani, Abolghasem
    Powiązania:
    https://bibliotekanauki.pl/articles/31340755.pdf
    Data publikacji:
    2016-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-transitive graph
    vertex-transitive graph
    lexicographic product of graphs
    Cartesian product of graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 4; 857-865
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The General Position Problem on Kneser Graphs and on Some Graph Operations
    Autorzy:
    Ghorbani, Modjtaba
    Maimani, Hamid Reza
    Momeni, Mostafa
    Mahid, Farhad Rahimi
    Klavžar, Sandi
    Rus, Gregor
    Powiązania:
    https://bibliotekanauki.pl/articles/32222714.pdf
    Data publikacji:
    2021-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    general position set
    Kneser graphs
    Cartesian product of graphs
    corona over graphs
    line graphs
    Opis:
    A vertex subset S of a graph G is a general position set of G if no vertex of S lies on a geodesic between two other vertices of S. The cardinality of a largest general position set of G is the general position number (gp-number) gp(G) of G. The gp-number is determined for some families of Kneser graphs, in particular for K(n, 2), n ≥ 4, and K(n, 3), n ≥ 9. A sharp lower bound on the gp-number is proved for Cartesian products of graphs. The gp-number is also determined for joins of graphs, coronas over graphs, and line graphs of complete graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1199-1213
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the rainbow connection of Cartesian products and their subgraphs
    Autorzy:
    Klavžar, Sandi
    Mekiš, Gašper
    Powiązania:
    https://bibliotekanauki.pl/articles/743307.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    rainbow connection
    strong rainbow connection
    Cartesian product of graphs
    isometric subgraph
    hypercube
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 4; 783-793
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On θ-graphs of partial cubes
    Autorzy:
    Klavžar, Sandi
    Kovse, Matjaz
    Powiązania:
    https://bibliotekanauki.pl/articles/743784.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    intersection graph
    partial cube
    median graph
    expansion theorem
    Cartesian product of graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 2; 313-321
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Rank numbers for bent ladders
    Autorzy:
    Richter, Peter
    Leven, Emily
    Tran, Anh
    Ek, Bryan
    Jacob, Jobby
    Narayan, Darren A.
    Powiązania:
    https://bibliotekanauki.pl/articles/30148235.pdf
    Data publikacji:
    2014-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph colorings
    rankings of graphs
    rank number
    Cartesian product of graphs
    ladder graph
    bent ladder graph
    Opis:
    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 $P_2 × P_n$. 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
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 2; 309-329
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    3-Tuple Total Domination Number of Rook’s Graphs
    Autorzy:
    Pahlavsay, Behnaz
    Palezzato, Elisa
    Torielli, Michele
    Powiązania:
    https://bibliotekanauki.pl/articles/32361755.pdf
    Data publikacji:
    2022-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k -tuple total domination
    Cartesian product of graphs
    rook’s graph
    Vizing’s conjecture
    Opis:
    A k-tuple total dominating set (kTDS) of a graph G is a set S of vertices in which every vertex in G is adjacent to at least k vertices in S. The minimum size of a kTDS is called the k-tuple total dominating number and it is denoted by γ×k,t(G). We give a constructive proof of a general formula for γ×3,t(Kn□Km).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 1; 15-37
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Minimal rankings of the Cartesian product Kₙ ☐ Kₘ
    Autorzy:
    Eyabi, Gilbert
    Jacob, Jobby
    Laskar, Renu
    Narayan, Darren
    Pillone, Dan
    Powiązania:
    https://bibliotekanauki.pl/articles/743282.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph colorings
    rankings of graphs
    minimal rankings
    rank number
    arank number
    Cartesian product of graphs
    rook's graph
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 4; 725-735
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    How Long Can One Bluff in the Domination Game?
    Autorzy:
    Brešar, Boštan
    Dorbec, Paul
    Klavžar, Sandi
    Košmrlj, Gašpar
    Powiązania:
    https://bibliotekanauki.pl/articles/31341979.pdf
    Data publikacji:
    2017-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination game
    game domination number
    bluff graphs
    minus graphs
    generalized Petersen graphs
    Kneser graphs
    Cartesian product of graphs
    Hamming graphs
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 2; 337-352
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
    Autorzy:
    Azarija, Jernej
    Powiązania:
    https://bibliotekanauki.pl/articles/30098147.pdf
    Data publikacji:
    2013-09-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Cartesian product graphs
    spanning trees
    number of spanning trees
    inequality
    Opis:
    Let $ G_1 $ and $ G_2 $ be simple graphs and let $ n_1 = |V (G_1)| $, $ m_1 = |E(G_1)| $ , $ n_2 = |V (G_2)|$ and $ m_2 = |E(G_2)|$. In this paper we derive sharp upper and lower bounds for the number of spanning trees $ \tau $ in the Cartesian product $ G_1 \square G_2 $ of $ G_1 $ and $ G_2 $. We show that: $$ \tau (G_1 \square G_2 ) \geq \frac{2(n_1-1)(n_2-1)}{n_1 n_2} (\tau (G_1) n_1 )^\frac{n_2+1}{2} (\tau(G_2)n_2)^\frac{n_1+1}{2} $$ and $$ \tau(G_1 \square G_2 ) \leq \tau (G_1) \tau (G_2) \left[ \frac{2m_1}{n_1-1} + \frac{2m_2}{n_2-1} \right]^{(n_1 - 1)(n_2 -1)} . $$ We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in $ K_{n_1} \square K_{n_2} $ which turns out to be $ n_1^{n_1-2} n_2^{n_2-2} (n_1 + n_2 )^{(n_1-1)(n_2-1)} $.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 4; 785-790
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-12 z 12

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies