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

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

Wyniki wyszukiwania

help Sortuj według:

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

Factoring directed graphs with respect to the cardinal product in polynomial time

100%
Imrich W., Klöckl W.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
593-601
EN
By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A prime factor theorem for a generalized direct product

100%
Imrich W., Stadler P.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
135-140
EN
We introduce the concept of neighborhood systems as a generalization of directed, reflexive graphs and show that the prime factorization of neighborhood systems with respect to the the direct product is unique under the condition that they satisfy an appropriate notion of thinness.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Factoring directed graphs with respect to the cardinal product in polynomial time II

100%
Imrich W., Klöckl W.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
461-474
EN
By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the thinness conditions and thus significantly extend the class of graphs for which the prime factorization can be found in polynomial time.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Tree-like isometric subgraphs of hypercubes

81%
Brešar B., Imrich W., Klavžar S.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
227-240
EN
Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Weak k-reconstruction of Cartesian products

81%
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
Content available remote

Edge-Transitive Lexicographic and Cartesian Products

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

Distinguishing Cartesian Products of Countable Graphs

71%
Estaji E., Imrich W., Kalinowski R., Pilśniak M., Tucker T.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
155-164
EN
The distinguishing number D(G) of a graph G is the minimum number of colors needed to color the vertices of G such that the coloring is preserved only by the trivial automorphism. In this paper we improve results about the distinguishing number of Cartesian products of finite and infinite graphs by removing restrictions to prime or relatively prime factors.
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ć.