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:  strong product
help Sortuj według:

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

Harary Index of Product Graphs

100%
Pattabiraman K., Paulraja P.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
17-33
EN
The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. In this paper, the exact formulae for the Harary indices of tensor product G × Km0,m1,...,mr−1 and the strong product G⊠Km0,m1,...,mr−1 , where Km0,m1,...,mr−1 is the complete multipartite graph with partite sets of sizes m0,m1, . . . ,mr−1 are obtained. Also upper bounds for the Harary indices of tensor and strong products of graphs are estabilished. Finally, the exact formula for the Harary index of the wreath product G ○ G′ is obtained.
2
Content available remote

Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs

100%
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.
3
Content available remote

2-Tone Colorings in Graph Products

100%
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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Edge-connectivity of strong products of graphs

100%
Bresar B., Spacapan S.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
333-343
EN
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.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The hull number of strong product graphs

100%
Santhakumaran A., Ullas Chandran S.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
493-507
EN
For a connected graph G with at least two vertices and S a subset of vertices, the convex hull $[S]_G$ is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with $[S]_G = V(G)$. Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs G and H for which h(G⊠ H) = h(G)h(H) are characterized.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

An upper bound of the basis number of the strong product of graphs

100%
Jaradat M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
391-406
EN
The basis number of a graph G is defined to be the least integer d such that there is a basis B of the cycle space of G such that each edge of G is contained in at most d members of B. In this paper we give an upper bound of the basis number of the strong product of a graph with a bipartite graph and we show that this upper bound is the best possible.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Wiener and vertex PI indices of the strong product of graphs

100%
Pattabiraman K., Paulraja P.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
749-769
EN
The Wiener index of a connected graph G, denoted by W(G), is defined as $½ ∑_{u,v ∈ V(G)}d_G(u,v)$. Similarly, the hyper-Wiener index of a connected graph G, denoted by WW(G), is defined as $½W(G) + ¼ ∑_{u,v ∈ V(G)} d²_G(u,v)$. The vertex Padmakar-Ivan (vertex PI) index of a graph G is the sum over all edges uv of G of the number of vertices which are not equidistant from u and v. In this paper, the exact formulae for Wiener, hyper-Wiener and vertex PI indices of the strong product $G ⊠ K_{m₀,m₁,...,m_{r -1}}$, where $K_{m₀,m₁,...,m_{r -1}}$ is the complete multipartite graph with partite sets of sizes $m₀,m₁, ...,m_{r -1}$, are obtained. Also lower bounds for Wiener and hyper-Wiener indices of strong product of graphs are established.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The strong isometric dimension of finite reflexive graphs

75%
Fitzpatrick S., Nowakowski R.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
23-38
EN
The strong isometric dimension of a reflexive graph is related to its injective hull: both deal with embedding reflexive graphs in the strong product of paths. We give several upper and lower bounds for the strong isometric dimension of general graphs; the exact strong isometric dimension for cycles and hypercubes; and the isometric dimension for trees is found to within a factor of two.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On dually compact closed classes of graphs and BFS-constructible graphs

51%
Polat N.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
365-381
EN
A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible graph. A (finite or infinite) graph G is constructible if there exists a well-ordering ≤ (called constructing ordering) of its vertices such that, for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Finite graphs are constructible if and only if they are dismantlable. The case is different, however, with infinite graphs. A graph G for which every breadth-first search of G produces a particular constructing ordering of its vertices is called a BFS-constructible graph. We show that the class of BFS-constructible graphs is a variety (i.e., it is closed under weak retracts and strong products), that it is a subclass of the class of weakly modular graphs, and that it contains the class of bridged graphs and that of Helly graphs (bridged graphs being very special instances of BFS-constructible graphs). Finally we show that the class of interval-finite pseudo-median graphs (and thus the one of median graphs) and the class of Helly graphs are dually compact closed, and that moreover every finite subgraph of an interval-finite pseudo-median graph (resp. a Helly graph) G is contained in a finite isometric pseudo-median (resp. Helly) subgraph of G. We also give two sufficient conditions so that a bridged graph has a similar property.
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ć.