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ę "product graph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 62
Tytuł:
Cancellation of direct products of digraphs
Autorzy:
Hammack, Richard
Toman, Katherine
Powiązania:
https://bibliotekanauki.pl/articles/744073.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph direct product
graph product cancellation
digraphs
Opis:
We investigate expressions of form A×C ≅ B×C involving direct products of digraphs. Lovász gave exact conditions on C for which it necessarily follows that A ≅ B. We are here concerned with a different aspect of cancellation. We describe exact conditions on A for which it necessarily follows that A ≅ B. In the process, we do the following: Given an arbitrary digraph A and a digraph C that admits a homomorphism onto an arc, we classify all digraphs B for which A×C ≅ B×C.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 575-590
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
Autorzy:
Sopena, Éric
Powiązania:
https://bibliotekanauki.pl/articles/743250.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
product graph
oriented coloring
oriented chromatic number
Opis:
The oriented chromatic number of an oriented graph $^→G$ is the minimum order of an oriented graph $^→H$ such that $^→G$ admits a homomorphism to $^→H$. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations.
In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^→U$ such that every orientation $^→G$ of G admits a homomorphism to $^→U$. We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of lexicographic, strong, Cartesian and direct products of graphs, and consider the particular case of products of paths.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 517-533
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Equitable coloring of graph products
Autorzy:
Furmańczyk, H.
Powiązania:
https://bibliotekanauki.pl/articles/254911.pdf
Data publikacji:
2006
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
equitable coloring
graph product
Opis:
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the "equitable chromatic number" of G and denoted by χ=(G). It is interesting to note that if a graph G is equitably k-colorable, it does not imply that it is equitably (k + 1)-colorable. The smallest integer k for which G is equitably k'-colorable for all k' ≥ k is called "the equitable chromatic threshold" of G and denoted by χ*=(G). In the paper we establish the equitable chromatic number and the equitable chromatic threshold for certain products of some highly-structured graphs. We extend the results from [2] for Cartesian, weak and strong tensor products.
Źródło:
Opuscula Mathematica; 2006, 26, 1; 31-44
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Wiener index of strong product of graphs
Autorzy:
Peterin, I.
Zigert-Pletersek, P.
Powiązania:
https://bibliotekanauki.pl/articles/255704.pdf
Data publikacji:
2018
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
Wiener index
graph product
strong product
Opis:
The Wiener index of a connected graph G is the sum of distances between all pairs of vertices of G. The strong product is one of the four most investigated graph products. In this paper the general formula for the Wiener index of the strong product of connected graphs is given. The formula can be simplified if both factors are graphs with the constant eccentricity. Consequently, closed formulas for the Wiener index of the strong product of a connected graph G of constant eccentricity with a cycle are derived.
Źródło:
Opuscula Mathematica; 2018, 38, 1; 81-94
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge-connectivity of strong products of graphs
Autorzy:
Bresar, Bostjan
Spacapan, Simon
Powiązania:
https://bibliotekanauki.pl/articles/743791.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connectivity
strong product
graph product
separating set
Opis:
The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ {1,2} either $x_i = y_i$ or $x_i y_i ∈ E(G_i)$. In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals min{δ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|)}. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 333-343
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Families of strongly projective graphs
Autorzy:
Larose, Benoit
Powiązania:
https://bibliotekanauki.pl/articles/743360.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance-transitive graphs
graph homomorphism
graph product
Opis:
We give several characterisations of strongly projective graphs which generalise in many respects odd cycles and complete graphs [7]. We prove that all known families of projective graphs contain only strongly projective graphs, including complete graphs, odd cycles, Kneser graphs and non-bipartite distance-transitive graphs of diameter d ≥ 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 2; 271-292
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A cancellation property for the direct product of graphs
Autorzy:
Hammack, Richard
Powiązania:
https://bibliotekanauki.pl/articles/743303.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph products
graph direct product
cancellation
Opis:
Given graphs A, B and C for which A×C ≅ B×C, it is not generally true that A ≅ B. However, it is known that A×C ≅ B×C implies A ≅ B provided that C is non-bipartite, or that there are homomorphisms from A and B to C. This note proves an additional cancellation property. We show that if B and C are bipartite, then A×C ≅ B×C implies A ≅ B if and only if no component of B admits an involution that interchanges its partite sets.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 179-184
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Centers of n-fold tensor products of graphs
Autorzy:
Bendall, Sarah
Hammack, Richard
Powiązania:
https://bibliotekanauki.pl/articles/744586.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph tensor product
graphs direct product
graph center
Opis:
Formulas for vertex eccentricity and radius for the n-fold tensor product $G = ⊗_{i=1} ⁿG_i$ of n arbitrary simple graphs $G_i$ are derived. The center of G is characterized as the union of n+1 vertex sets of form V₁×V₂×...×Vₙ, with $V_i ⊆ V(G_i)$.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 491-501
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Grundy number of graphs
Autorzy:
Effantin, Brice
Kheddouci, Hamamache
Powiązania:
https://bibliotekanauki.pl/articles/743619.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Grundy coloring
vertex coloring
cartesian product
graph product
Opis:
The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, 1 ≤ i ≤ k, is adjacent to (i-1) vertices colored with each color j, 1 ≤ j ≤ i -1. In this paper we give bounds for the Grundy number of some graphs and cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally, we present an algorithm to generate all graphs for a given Grundy number.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 5-18
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Recognizing weighted directed cartesian graph bundles
Autorzy:
Zmazek, Blaz
Zerovnik, Janez
Powiązania:
https://bibliotekanauki.pl/articles/743682.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph bundles
Cartesian graph product
weighted digraphs
half-convexity
Opis:
In this paper we show that methods for recognizing Cartesian graph bundles can be generalized to weighted digraphs. The main result is an algorithm which lists the sets of degenerate arcs for all representations of digraph as a weighted directed Cartesian graph bundle over simple base digraphs not containing transitive tournament on three vertices. Two main notions are used. The first one is the new relation $^→δ*$defined among the arcs of a digraph as a weighted directed analogue of the well-known relation δ*. The second one is the concept of half-convex subgraphs. A subgraph H is half-convex in G if any vertex x ∈ G∖H has at most one predecessor and at most one successor.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 1; 39-56
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Grundy Total Domination Number in Product Graphs
Autorzy:
Brešar, Boštjan
Bujtás, Csilla
Gologranc, Tanja
Klavžar, Sandi
Košmrlj, Gašper
Marc, Tilen
Patkós, Balázs
Tuza, Zsolt
Vizer, Máté
Powiązania:
https://bibliotekanauki.pl/articles/32083828.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
Grundy total domination number
graph product
Opis:
A longest sequence $(v_1, . . ., v_k)$ of vertices of a graph $G$ is a Grundy total dominating sequence of $G$ if for all $i$, \(N(υ_i)\backslash\bigcup_{j=1}^{i-1}N(υ_j)≠∅\). The length $k$ of the sequence is called the Grundy total domination number of $G$ and denoted $\gamma_{gr}^t(G)$. In this paper, the Grundy total domination number is studied on four standard graph products. For the direct product we show that $\gamma_{gr}^t(G×H)≥\gamma_{gr}^t(G)\gamma_{gr}^t(H)$, conjecture that the equality always holds, and prove the conjecture in several special cases. For the lexicographic product we express $\gamma_{gr}^t(G∘H)$ in terms of related invariant of the factors and find some explicit formulas for it. For the strong product, lower bounds on $\gamma_{gr}^t(G⊠H)$ are proved as well as upper bounds for products of paths and cycles. For the Cartesian product we prove lower and upper bounds on the Grundy total domination number when factors are paths or cycles.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 225-247
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total connected domination game
Autorzy:
Bujtás, Csilla
Henning, Michael A.
Iršič, Vesna
Klavžar, Sandi
Powiązania:
https://bibliotekanauki.pl/articles/2050904.pdf
Data publikacji:
2021
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
connected domination game
total connected domination game
graph product
tree
Opis:
The (total) connected domination game on a graph $G$ is played by two players, Dominator and Staller, according to the standard (total) domination game with the additional requirement that at each stage of the game the selected vertices induce a connected subgraph of $G$. If Dominator starts the game and both players play optimally, then the number of vertices selected during the game is the (total) connected game domination number $(\gamma_{tcg}(G))(\gamma_{cg(G)})$ of $G$. We show that $\gamma_{tcg}(G) \in \{\gamma_{cg}(G), \gamma_{cg}(G)+1, \gamma_{cg}(G)+2\}$, and consequently define $G$ as Class $i$ if $\gamma_{tcg}(G) = \gamma_{cg}(G)+i$ for $i \in \{0, 1, 2\}$. A large family of Class 0 graphs is constructed which contains all connected Cartesian product graphs and connected direct product graphs with minimum degree at least 2. We show that no tree is Class 2 and characterize Class 1 trees. We provide an infinite family of Class 2 bipartite graphs.
Źródło:
Opuscula Mathematica; 2021, 41, 4; 453-464
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Isomorphic components of direct products of bipartite graphs
Autorzy:
Hammack, Richard
Powiązania:
https://bibliotekanauki.pl/articles/743937.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
direct product
tensor product
Kronecker product
bipartite graph
Opis:
A standard result states the direct product of two connected bipartite graphs has exactly two components. Jha, Klavžar and Zmazek proved that if one of the factors admits an automorphism that interchanges partite sets, then the components are isomorphic. They conjectured the converse to be true. We prove the converse holds if the factors are square-free. Further, we present a matrix-theoretic conjecture that, if proved, would prove the general case of the converse; if refuted, it would produce a counterexample.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 231-248
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Vizings conjecture
Autorzy:
Bresar, Bostjan
Powiązania:
https://bibliotekanauki.pl/articles/743820.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
Cartesian product
domination number
Opis:
A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 1; 5-11
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Products Of Digraphs And Their Competition Graphs
Autorzy:
Sonntag, Martin
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/31341180.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
competition graph
product of digraphs
Opis:
If D = (V, A) is a digraph, its competition graph (with loops) CGl(D) has the vertex set V and {u, v} ⊆ V is an edge of CGl(D) if and only if there is a vertex w ∈ V such that (u, w), (v, w) ∈ A. In CGl(D), loops {v} are allowed only if v is the only predecessor of a certain vertex w ∈ V. For several products D1 ⚬ D2 of digraphs D1 and D2, we investigate the relations between the competition graphs of the factors D1, D2 and the competition graph of their product D1 ⚬ D2.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 43-58
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 62

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