Circuit preserving edge maps

It is proved that any one-to-one edge map f from a 3-connected graph G onto a graph G′, G and G′ possibly infinite, satisfying f(C) is a circuit in G′ whenever C is a circuit in G is induced by a vertex isomorphism. This generalizes a result of Whitney which hypothesizes f(C) is a circuit in G′ if and only if C is a circuit in G.     

Subgraphs as circuits and bases of matroids

As is well known, the cycles of any given graph G may be regarded as the circuits of a matroid defined on the edge set of G. The question of whether other families of connected graphs exist such that, given any graph G, the subgraphs of G isomorphic to some member of the family may be regarded as the circuits of a matroid defined on the edge set of G led us, in two other papers, to the proof of some results concerning properties of the cycles when regarded as circuits of such matroids. Here we prove that the wheels share many of these properties with the cycles. Moreover, properties of subgraphs which may be regarded as bases of such matroids are also investigated.     

Surface basic sets with wildly embedded supporting surfaces

The situation where a “nice” diffeomorphism f of a 3-manifold has a wildly embedded invariant surfaceM for which the restriction g = f| _M : M → M is “nice” is considered.     

Properties of Hamilton cycles of circuit graphs of matroids

Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55: 654–659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e′ for any two edges e and e′ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.     

Panconnectivity for interconnection networks with faulty elements

Let Go and G1 be two graphs with the same vertices. The new graph G（G0, G1; M） is a graph with the vertex set V（0o） ∪）V（G1） and the edge set E（Go） UE（G1） UM, where M is an arbitrary perfect matching between the vertices of Go and G1, i.e., a set of cross edges with one endvertex in Go and the other endvertex in G1. In this paper, we will show that if Go and G1 are f-fault q-panconnected, then for any f 〉 2, G（G0, G1; M） is （f ＋ 1）-fault （q ＋ 2）-panconnected.     

NP-completeness for minimizing maximum edge length in grid embeddings

Given an embedding f: G →$\text{Z}$² of a graph G in the two-dimensional lattice, let |f| be the maximum L₁ distance between points f(x) and f(y) where xy is an edge of G. Let B₂(G) be the minimum |f| over all embeddings f. It is shown that the determination of B₂(G) for arbitrary G is NP-complete. Essentially the same proof can be used in showing the NP-completeness of minimizing |f| over all embeddings f: G → $\text{Z}$ⁿ of G into the n-dimensional integer lattice for any fixed n ≥ 2.     

On the Super Edge-Magic Deficiency of Graphs

A (p, q) graph G is edge-magic if there exists a bijective function f: V(G) ∪ E(G) → {1,2,…,p + q} such that f(u) + f(v) + f(uv) = k is a constant, called the valence of f, for any edge uv of G. Moreover, G is said to be super edge-magic if f(V(G)) = {1,2,…,p}. The question studied in this paper is for which graphs is it possible to add a finite number of isolated vertices so that the resulting graph is super edge-magic? If it is possible for a given graph G, then we say that the minimum such number of isolated vertices is the super edge-magic deficiency, μ_s(G) of G; otherwise we define it to be + ∞.     

Removing circuits in 3-connected binary matroids

For a k-connected graph or matroid M, where k is a fixed positive integer, we say that a subset X of E(M) is k-removable provided M?X is k-connected. In this paper, we obtain a sharp condition on the size of a 3-connected binary matroid to have a 3-removable circuit.     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

Nowhere zero flow and circuit covering in regular matroids

Let s(k) be the smallest s such that if there exists a k-nowhere zero flow in a regular matroid M, then M can be covered by circuits, the total length of which is at most s|M|. A recursive formula for the evaluation of s(k) is given: $\text{s(kt) ≤}\text{(s(k)(kt ? t) + s(t)(kt ? k))}\text{(kt ? 1)}$. By means of this formula s(k) is found for k = 2, 3, 4, 6, 7, 8. “Natural” proofs for graph theoretical results are obtained.     

Sequentially additive graphs

The concept of a simply sequentially additive graph is introduced as follows. A graph G with |V(G)|+|E(G)|=M is said to be simply sequentially additive if there is a bijection f:V(G)∪E(G)→{;1,2,…,M}; such that for each x = (u, ν) in E(G), f(x) = f(u) + f(ν). Various aspects of finding such numberinga or showing that none exist are discussed.     

Induced Hamiltonian maps on the symplectic quotient

Let (M,ω) be a symplectic manifold and G a compact Lie group that acts on M. Assume that the action of G on M is Hamiltonian. Then a G-equivariant Hamiltonian map on M induces a map on the symplectic quotient of M by G. Consider an autonomous Hamiltonian H with compact support on M, with no non-constant closed trajectory in time less than 1 and time-1 map fH. If the map fH descends to the symplectic quotient to a map Φ(fH) and the symplectic manifold M is exact and Ham(M,ω) has no short loops, we prove that the Hofer norm of the induced map Φ(fH) is bounded above by the Hofer norm of fH.     

Refinable and monotone maps revisited

Generalizing results by J. Ford, J. W. Rogers, Jr. and H. Kato we prove that (1) a map f from a G-like continuum onto a graph G is refinable iff f is monotone; (2) a graph G is an arc or a simple closed curve iff every G-like continuum that contains no nonboundary indecomposable subcontinuum admits a monotone map onto G.We prove that if bonding maps in the inverse sequence of compact spaces are refinable then the projections of the inverse limit onto factor spaces are refinable. We use this fact to show that refinable maps do not preserve completely regular or totally regular continua.     

Vector representable matroids of given rank with given automorphism group

A simple way of associating a matroid of prescribed rank with a graph is shown. The matroids so constructed are representable over any sufficiency large field. Their use is demonstrated by the following result: Given an integer k?3 and a function G associating a group with each subset of a set S, there is a matroid M(E), representable over any sufficiently large field, such that E ? S, and for any T ?/ S, the rank of M/Tis k, and the automorphine group of MT is isomorphic to G(T).     

Ordinals and set-valued zero-selections for hyperspaces

A continuous zero-selection f for the Vietoris hyperspace F(X) of the nonempty closed subsets of a space X is a Vietoris continuous map f:F(X)→X which assigns to every nonempty closed subset an isolated point of it. It is well known that a compact space X has a continuous zero-selection if and only if it is an ordinal space, or, equivalently, if X can be mapped onto an ordinal space by a continuous one-to-one surjection. In this paper, we prove that a compact space X has an upper semi-continuous set-valued zero-selection for its Vietoris hyperspace F(X) if and only if X can be mapped onto an ordinal space by a continuous finite-to-one surjection.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

The connectivity and minimum degree of circuit graphs of matroids

Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.     

The Connectivity and Diameter of Second Order Circuit Graphs of Matroids

Let C ₂(M) be the second order circuit graph of a simple connected matroid M, then C ₂(M) is 2-connected if M has more than one circuit and M is not a line. Moreover, C ₂(M) has diameter at most two if and only if M does not have any restriction isomorphic to U _2,6.     

Piecewise Endomorphisms of Pid-Modules

Let G be a finitely generated module over a PID, D. We investigate the structure of the centralizer near-ring M_D(G) = {f: G → G ¦ f(ar) = (fa)r,a ∈ G, r ∈ D}. If C = {G_α} is a cover of G by maximal cyclic submodules then we show that every f ∈ M_D(G) is piecewise an endomorphism of G.     

Graph maps whose periodic points form a closed set

A continuous map f from a graph G to itself is called a graph map. Denote by P(f), R(f), ω(f), Ω(f) and CR(f) the sets of periodic points, recurrent points, ω-limit points, non-wandering points and chain recurrent points of f respectively. It is well known that P(f)⊂R(f)⊂ω(f)⊂Ω(f)⊂CR(f). Block and Franke (1983) [5] proved that if f:I→I is an interval map and P(f) is a closed set, then CR(f)=P(f). In this paper we show that if f:G→G is a graph map and P(f) is a closed set, then ω(f)=R(f). We also give an example to show that, for general graph maps f with P(f) being a closed set, the conclusion ω(f)=R(f) cannot be strengthened to Ω(f)=R(f) or ω(f)=P(f).