Distinguishing infinite graphs.
Graphen mit transitiver Automorphismengruppe.
Zehnpunktige kubische Graphen
Zehnpunktige Kubische Graphen. (Short Communication).
Abelian groups with identical relations
Charakterisierung von Gruppenklassen mit Hilfe der inversen Operation.
Das lexikographische Produkt gerichteter Graphen.
On the Lexicographic and Costrong Product of Set Systems. (Über das lexikographische und das kostrake Produkt von Mengensystemen) (Short Communication)
Über das lexikographische und das Kostarke Produkt von Mengensystemen
Factoring directed graphs with respect to the cardinal product in polynomial time
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.
Factoring directed graphs with respect to the cardinal product in polynomial time II
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...
Classification of tensor products of symmetric graphs
In the category of symmetric graphs there are exactly five closed tensor products. If we omit the requirement of units, we obtain twelve more.
Transitive planar graphs
Weak k-reconstruction of Cartesian products
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...
Tree-like isometric subgraphs of hypercubes
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...
A prime factor theorem for a generalized direct product
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.
Edge-Transitive Lexicographic and Cartesian Products
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...
Distinguishing Cartesian Products of Countable Graphs
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.
Page 1