Informacja

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

Wyszukujesz frazę "Imrich, Wilfried" wg kryterium: Autor


Wyświetlanie 1-7 z 7
Tytuł:
Factoring directed graphs with respect to the cardinal product in polynomial time
Autorzy:
Imrich, Wilfried
Klöckl, Werner
Powiązania:
https://bibliotekanauki.pl/articles/743472.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
directed graphs
cardinal product
graph algorithms
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 593-601
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A prime factor theorem for a generalized direct product
Autorzy:
Imrich, Wilfried
Stadler, Peter
Powiązania:
https://bibliotekanauki.pl/articles/743894.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
products
set systems
prime factor theorem
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 135-140
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Factoring directed graphs with respect to the cardinal product in polynomial time II
Autorzy:
Imrich, Wilfried
Klöckl, Werner
Powiązania:
https://bibliotekanauki.pl/articles/744038.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
directed graphs
cardinal product
graph algorithms
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 461-474
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Tree-like isometric subgraphs of hypercubes
Autorzy:
Brešar, Bostjan
Imrich, Wilfried
Klavžar, Sandi
Powiązania:
https://bibliotekanauki.pl/articles/743405.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
isometric embeddings
partial cubes
expansion procedures
trees
median graphs
graph automorphisms
automorphism groups
dismantlable graphs
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 227-240
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Weak k-reconstruction of Cartesian products
Autorzy:
Imrich, Wilfried
Zmazek, Blaz
Zerovnik, Janez
Powiązania:
https://bibliotekanauki.pl/articles/743162.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
reconstruction problem
Cartesian product
composite graphs
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 273-285
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ł:
Distinguishing Cartesian Products of Countable Graphs
Autorzy:
Estaji, Ehsan
Imrich, Wilfried
Kalinowski, Rafał
Pilśniak, Monika
Tucker, Thomas
Powiązania:
https://bibliotekanauki.pl/articles/31342144.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex coloring
distinguishing number
automorphisms
infinite graphs
Cartesian and weak Cartesian product
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 155-164
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-7 z 7

    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