Zur Lösung einer Klasse von Gleichungen mit einem monotonen Potentialoperator

This paper is concerned with terminable and interminable paths and trails in infinite graphs. It is shown that

• The only connected graphs which contain no 2 – ∞ way and in which no finite path is terminable are precisely all the 1 – ∞ multiways.
• The only connected graphs which have no 2 – ∞ trail and in which no finite trail is terminable are precisely all the 1 – ∞ multiways all of whose multiplicities are odd numbers and which have infinitely many bridges.
• In addition the strucuture of those connected graphs is determined which have a 1 – ∞ trail and in which no 1 – ∞ trail but every finite trail is terminable.

In this paper the terminology and notation of a previous paper of the writer [1] and of F. HARARY 's book [6] will be used. Furthermore, a graph consisting of the distinct nodes n₁,…,n_δ (where δ≧1) and of one or more (n_i, n_i+1)-edges for i = 1,…, δ – 1 will be called a multiway, and analogously for 1 – ∞ and 2 – ∞ multiways. The number of edges joining n_i and n_i+1 will be called the (n_i,+1)-multiplicity. Thus a multiway in which each multiplicity is 1 is a way. Multiplicities are allowed to be infinite.     

A Ramsey-type theorem for traceable graphs

A graph G is traceable if there is a path passing through all the vertices of G. It is proved that every infinite traceable graph either contains arbitrarily large finite chordless paths, or contains a subgraph isomorphic to graph A, illustrated in the text. A corollary is that every finitely generated infinite lattice of length 3 contains arbitrarily large finite fences. It is also proved that every infinite traceable graph containing no chordless four-point path contains a subgraph isomorphic to K_ω,ω. The versions of these results for finite graphs are discussed.     

An edge-deletion problem for locally finite graphs

For each positive integer n, let T_n be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs T_n is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T₂, the oneway infinite path T₁ is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T₁ is also the only stable graph.     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class.     

On Hamilton decompositions of infinite circulant graphs

The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .     

Invariant Hamming graphs in infinite quasi-median graphs

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming graph.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

Connected Q-integral graphs with maximum edge-degree less than or equal to 8

Graphs with integral signless Laplacian spectrum are called Q-integral graphs. The number of adjacent edges to an edge is defined as the edge-degree of that edge. The Q-spectral radius of a graph is the largest eigenvalue of its signless Laplacian. In 2019, Park and Sano [16] studied connected Q-integral graphs with the maximum edge-degree at most six. In this article, we extend their result and study the connected Q-integral graphs with maximum edge-degree less than or equal to eight. Further, we give an upper bound and a lower bound for the maximum edge-degree of a connected Q-integral graph with respect to its Q-spectral radius. As a corollary, we show that the Q-spectral radius of the connected edge-non-regular Q-integral graph with maximum edge-degree five is six, which we anticipate to be a key for solving the unsolved problem of characterizing such graphs.     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

Graphoidal bipartite graphs

A graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths inG such that every path in ψ has at least two vertices, every vertex ofG is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. Let Ω (ψ) denote the intersection graph of ψ. A graph G is said to be graphoidal if there exists a graphH and a graphoidal cover ψof H such that G is isomorphic to Ω(ψ). In this paper we study the properties of graphoidal graphs and obtain a forbidden subgraph characterisation of bipartite graphoidal graphs.     

Menger's Theorem for Graphs Containing no Infinite Paths

Menger's theorem can be stated as follows: Let G = (V, E) be a finite graph, and let A and B be subsets of V. Then there exists a family F of vertex-disjoint paths from A to B and a subset S of V which separates A and B, such that S consists of a choice of precisely one vertex from each path in F.Erdös conjectured that in this form the theorem can be extended to infinite graphs. We prove this to be true for graphs containing no infinite paths, by showing that in this case the problem can be reduced to the case of bipartite graphs.     

An extension of Sallee’s theorem to infinite locally finite vap-free plane graphs

A graph isk-cyclable if givenk vertices there is a cycle that contains thek vertices. Sallee showed that every finite 3-connected planar graph is 5-cyclable. In this paper, by characterizing the circuit graphs and investigating the structure of LV-graphs, we extend his result to 3-connected infinite locally finite VAP-free plane graphs.     

Note on infinite graphs

Some relations between the number of nodes and edges and the degrees of the nodes in infinite graphs are obtained. The structure of infinite connected graphs which have no- ∞ trails is investigated with the help of these. It is shown, for example, that any such graph G has |G| nodes of odd degree.     

One-way infinite hamiltonian paths in infinite maximal planar graphs

A one-way infinite Hamiltonian path is constructed in an infinite 4-connected VAP-free maximal planar graph containing one or two vertices of infinite degree. Combining this result and that of R. HALIN who investigated the structure of such graphs, we conclude that such a path always exists in every infinite 4-connected maximal planar graph with exactly one end, which is an extension of H. WHITNEY'S theorem to infinite graphs.     

Spanning 2‐trails from degree sum conditions

Suppose G is a simple connected n‐vertex graph. Let σ₃(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ₃G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K_1,3. Second, if σ₃(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ₃(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K_2,3 or K (the 6‐vertex graph obtained from K_2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004     

Rectangular and visibility representations of infinite planar graphs

We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a horizontal or vertical straight line segment, and such that no two edges cross. A result of Tamassia and Tollis extends as follows: Every countably infinite planar graph is a subgraph of a visibility graph. Furthermore, every locally finite, 2‐connected, planar graph is a visibility graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 257–265, 2006     

Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.