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

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

Wyniki wyszukiwania

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graphs with convex domination number close to their order

100%
Cyman J., Lemańska M., Raczek J.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
307-316
EN
For a connected graph G = (V,E), a set D ⊆ V(G) is a dominating set of G if every vertex in V(G)-D has at least one neighbour in D. The distance $d_G(u,v)$ between two vertices u and v is the length of a shortest (u-v) path in G. An (u-v) path of length $d_G(u,v)$ is called an (u-v)-geodesic. A set X ⊆ V(G) is convex in G if vertices from all (a-b)-geodesics belong to X for any two vertices a,b ∈ X. A set X is a convex dominating set if it is convex and dominating. The convex domination number $γ_{con}(G)$ of a graph G is the minimum cardinality of a convex dominating set in G. Graphs with the convex domination number close to their order are studied. The convex domination number of a Cartesian product of graphs is also considered.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Improving some bounds for dominating Cartesian products

80%
Hartnell B., Rall D.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
261-272
EN
The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds for dominating the Cartesian product of any two graphs. We show how it is possible to improve some of these bounds by imposing conditions on both graphs. For example, we establish a new lower bound for the domination number of T T, when T is a tree, and we improve an upper bound of Vizing in the case when one of the graphs has k > 1 dominating sets which cover the vertex set and the other has a dominating set which partitions in a certain way.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Vizing's conjecture and the one-half argument

80%
Hartnell B., Rall D.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 2
205-216
EN
The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as well as the collection of graphs considered by Barcalkin and German in [1]. A crucial part of the proof depends on the well-known fact that the domination number of any connected graph of order at least two is no more than half its order.
4
Content available remote

On the Domination of Cartesian Product of Directed Cycles: Results for Certain Equivalence Classes of Lengths

80%
Mollard M.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
387-394
EN
Let (−→ Cm2−→ Cn) be the domination number of the Cartesian product of directed cycles −→ Cm and −→ Cn for m, n ≥ 2. Shaheen [13] and Liu et al. ([11], [12]) determined the value of (−→ Cm2−→ Cn) when m ≤ 6 and [12] when both m and n ≡ 0(mod 3). In this article we give, in general, the value of (−→ Cm2−→ Cn) when m ≡ 2(mod 3) and improve the known lower bounds for most of the remaining cases. We also disprove the conjectured formula for the case m ≡ 0(mod 3) appearing in [12].
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Weak k-reconstruction of Cartesian products

80%
Imrich W., Zmazek B., Zerovnik J.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
273-285
EN
By Ulam's conjecture every finite graph G can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of k-vertex deleted subgraphs of Cartesian products, and prove that one can decide whether a graph H is a k-vertex deleted subgraph of a Cartesian product G with at least k+1 prime factors on at least k+1 vertices each, and that H uniquely determines G. This extends previous work of the authors and Sims. The paper also contains a counterexample to a conjecture of MacAvaney.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On Vizing's conjecture

80%
Bresar B.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
5-11
EN
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.
7
Content available remote

Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs

80%
Sun Y.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
833-843
EN
The generalized k-connectivity κk(G) of a graph G was introduced by Hager in 1985. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λk(G) = min{λ(S) : S ⊆ V (G) and |S| = k}, where λ(S) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . . , Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp upper bounds for the generalized 3-edge-connectivity of Cartesian product graphs and strong product graphs. Among our results, some special cases are also discussed.
8
Content available remote

2-Tone Colorings in Graph Products

80%
Loe J., Middelbrooks D., Morris A., Wash K.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
55-72
EN
A variation of graph coloring known as a t-tone k-coloring assigns a set of t colors to each vertex of a graph from the set {1, . . . , k}, where the sets of colors assigned to any two vertices distance d apart share fewer than d colors in common. The minimum integer k such that a graph G has a t- tone k-coloring is known as the t-tone chromatic number. We study the 2-tone chromatic number in three different graph products. In particular, given graphs G and H, we bound the 2-tone chromatic number for the direct product G×H, the Cartesian product G□H, and the strong product G⊠H.
9
Content available remote

The Domination Number of K3n

80%
Georges J., Lin J., Mauro D.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
629-632
EN
Let K3n denote the Cartesian product Kn□Kn□Kn, where Kn is the complete graph on n vertices. We show that the domination number of K3n is [...]
10
Content available remote

On Two Generalized Connectivities of Graphs

80%
Sun Y., Li F., Jin Z.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
245-261
EN
The concept of generalized k-connectivity κk(G), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity τk(G) was also introduced by Hager in 1985, which is a specialization of generalized k-connectivity but a generalization of the classical connectivity. Another generalized connectivity of a graph G, named k-connectivity κ′k(G), introduced by Chartrand et al. in 1984, is a generalization of the cut-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of κ′k(G) and τk(G) by showing that for a connected graph G of order n, if κ′k(G) ≠ n − k + 1 where k ≥ 3, then 1 ≤ κ′k(G) − τk(G) ≤ n − k; otherwise, 1 ≤ κ′k(G) ‘− τk(G) ≤ n − k + 1. Moreover, all of these bounds are sharp. We get a sharp upper bound for the 3-connectivity of the Cartesian product of any two connected graphs with orders at least 5. Especially, the exact values for some special cases are determined. Among our results, we also study the pendant tree-connectivity of Cayley graphs on Abelian groups of small degrees and obtain the exact values for τk(G), where G is a cubic or 4-regular Cayley graph on Abelian groups, 3 ≤ k ≤ n.
11
Content available remote

The Thickness of Amalgamations and Cartesian Product of Graphs

80%
Yang Y., Chen Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
561-572
EN
The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is a measurement of the closeness to the planarity of a graph, and it also has important applications to VLSI design, but it has been known for only few graphs. We obtain the thickness of vertex-amalgamation and bar-amalgamation of graphs, the lower and upper bounds for the thickness of edge-amalgamation and 2-vertex-amalgamation of graphs, respectively. We also study the thickness of Cartesian product of graphs, and by using operations on graphs, we derive the thickness of the Cartesian product Kn □ Pm for most values of m and n.
12
Content available remote

Prime Factorization And Domination In The Hierarchical Product Of Graphs

80%
Anderson S. E., Guob Y., Tenney A., Wash K. A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 4
873-890
EN
In 2009, Barrière, Dalfó, Fiol, and Mitjana introduced the generalized hierarchical product of graphs. This operation is a generalization of the Cartesian product of graphs. It is known that every connected graph has a unique prime factor decomposition with respect to the Cartesian product. We generalize this result to show that connected graphs indeed have a unique prime factor decomposition with respect to the generalized hierarchical product. We also give preliminary results on the domination number of generalized hierarchical products.
13
Content available remote

Topological Manifolds

80%
Pąk K.
Formalized Mathematics
|
2014
|
tom 22
|
nr 2
179-186
EN
Let us recall that a topological space M is a topological manifold if M is second-countable Hausdorff and locally Euclidean, i.e. each point has a neighborhood that is homeomorphic to an open ball of E n for some n. However, if we would like to consider a topological manifold with a boundary, we have to extend this definition. Therefore, we introduce here the concept of a locally Euclidean space that covers both cases (with and without a boundary), i.e. where each point has a neighborhood that is homeomorphic to a closed ball of En for some n. Our purpose is to prove, using the Mizar formalism, a number of properties of such locally Euclidean spaces and use them to demonstrate basic properties of a manifold. Let T be a locally Euclidean space. We prove that every interior point of T has a neighborhood homeomorphic to an open ball and that every boundary point of T has a neighborhood homeomorphic to a closed ball, where additionally this point is transformed into a point of the boundary of this ball. When T is n-dimensional, i.e. each point of T has a neighborhood that is homeomorphic to a closed ball of En, we show that the interior of T is a locally Euclidean space without boundary of dimension n and the boundary of T is a locally Euclidean space without boundary of dimension n − 1. Additionally, we show that every connected component of a compact locally Euclidean space is a locally Euclidean space of some dimension. We prove also that the Cartesian product of locally Euclidean spaces also forms a locally Euclidean space. We determine the interior and boundary of this product and show that its dimension is the sum of the dimensions of its factors. At the end, we present several consequences of these results for topological manifolds. This article is based on [14].
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total domination of Cartesian products of graphs

80%
Hou X.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
175-178
EN
Let γₜ(G) and $γ_{pr}(G)$ denote the total domination and the paired domination numbers of graph G, respectively, and let G □ H denote the Cartesian product of graphs G and H. In this paper, we show that γₜ(G)γₜ(H) ≤ 5γₜ(G □ H), which improves the known result γₜ(G)γₜ(H) ≤ 6γₜ(G □ H) given by Henning and Rall.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Paired domination in prisms of graphs

80%
Mynhardt C., Schurch M.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
5-23
EN
The paired domination number $γ_{pr}(G)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: $γ_{pr}(πG) = 2γ_{pr}(G)$ for all πG; $γ_{pr}(K₂☐ G) = 2γ_{pr}(G)$; $γ_{pr}(K₂☐ G) = γ_{pr}(G)$.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The crossing numbers of certain Cartesian products

71%
Klešč M.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 1
5-10
EN
In this article we determine the crossing numbers of the Cartesian products of given three graphs on five vertices with paths.
17
Content available remote

On the Crossing Numbers of Cartesian Products of Wheels and Trees

71%
Klešč M., Petrillová J., Valo M.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
399-413
EN
Bokal developed an innovative method for finding the crossing numbers of Cartesian product of two arbitrarily large graphs. In this article, the crossing number of the join product of stars and cycles are given. Afterwards, using Bokal’s zip product operation, the crossing numbers of the Cartesian products of the wheel Wn and all trees T with maximum degree at most five are established.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some crossing numbers of products of cycles

71%
Klešč M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
197-210
EN
The exact values of crossing numbers of the Cartesian products of four special graphs of order five with cycles are given and, in addition, all known crossing numbers of Cartesian products of cycles with connected graphs on five vertices are summarized.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the crossing numbers of G □ Cₙ for graphs G on six vertices

71%
Draženská E., Klešč M.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
239-252
EN
The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G☐Cₙ for some graphs G on five and six vertices and the cycle Cₙ are also given. In this paper, we extend these results by determining crossing numbers of Cartesian products G☐Cₙ for some connected graphs G of order six with six and seven edges. In addition, we collect known results concerning crossing numbers of G☐Cₙ for graphs G on six vertices.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Notes on the independence number in the Cartesian product of graphs

71%
Abay-Asmerom G., Hammack R., Larson C., Taylor D.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
25-35
EN
Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H) for the independence number and we classify graphs for which equality holds. The second part of the paper concerns independence irreducibility. It is known that every graph G decomposes into a König-Egervary subgraph (where the independence number and the matching number sum to the number of vertices) and an independence irreducible subgraph (where every non-empty independent set I has more than |I| neighbors). We examine how this decomposition relates to the Cartesian product. In particular, we show that if one of G or H is independence irreducible, then G ☐ H is independence irreducible.
first rewind previous Strona / 2 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ć.