Circuit preserving edge maps II

In Section 1 of this article we prove the following. Let f: G → G′ be a circuit surjection, i.e., a mapping of the edge set of G onto the edge set of G′ which maps circuits of G onto circuits of G′, where G, G′ are graphs without loops or multiple edges and G′ has no isolated vertices. We show that if G is assumed finite and 3-connected, then f is induced by a vertex isomorphism. If G is assumed 3-connected but not necessarily finite and G′ is assumed to not be a circuit, then f is induced by a vertex isomorphism. Examples of circuit surjections f: G → G′ where G′ is a circuit and G is an infinite graph of arbitrarily large connectivity are given. In general if we assume G two-connected and G′ not a circuit then any circuit surjection f: G → G′ may be written as the composite of three maps, f(G) = q(h(k(G))), where k is a 1-1 onto edge map which preserves circuits in both directions (the “2-isomorphism” of Whitney (Amer. J. Math. 55 (1933), 245–254) when G is finite), h is an onto edge map obtained by replacing “suspended chains” of k(G) with single edges, and G is a circuit injection (a 1-1 circuit surjection). Let f: G → M be a 1-1 onto mapping of the edges of G onto the cells of M which takes circuits of G onto circuits of M where G is a graph with no isolated vertices, M a matroid. If there exists a circuit C of M which is not the image of a circuit in G, we call f nontrivial, otherwise trivial. In Section 2 we show the following. Let G be a graph of even order. Then the statement “no trivial map f: G → M exists, where M is a binary matroid,” is equivalent to “G is Hamiltonian.” If G is a graph of odd order, then the statement “no nontrivial map f: G → M exists, where M is a binary matroid” is equivalent to “G is almost Hamiltonian,” where we define a graph G of order n to be almost Hamiltonian if every subset of vertices of order n − 1 is contained in some circuit of G.     

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.     

On removable even circuits in graphs

Let G be a connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G such that G−E(C) is either connected or contains precisely two components one of which is isomorphic to a 1-bond. We further prove sufficient conditions for there to exist an even circuit C in a 2-connected simple graph G such that G−E(C) is 2-connected. As a consequence of this, we obtain sufficient conditions for there to exist an even circuit C in a 2-connected graph G for which G−E(C) is 2-connected.     

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 + ∞.     

A note on similar edges and edge-unique line graphs

If G is a connected graph having no vertices of degree 2 and L(G) is its line graph, two results are proven: if there exist distinct edges e and f with L(G) ? e ? L(G) ? f then there is an automorphism of L(G) mapping e to f; if $\text{G ? u ¦ G ? v}$ for any distinct vertices u, v, then $\text{L(G) ? e ¦ L(G) ? f}$ for any distinct edges e, f.     

Adjacent strong edge coloring of graphs

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where $\text{C(u) = {ƒ(uv) | uv ∈ E}}$, then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′_as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′_as(G), and obtain the χ′_as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′_as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.     

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.     

Upper minus total domination in small-degree regular graphs

A function f:V(G)→{-1,0,1} defined on the vertices of a graph G is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. An MTDF f is minimal if there does not exist an MTDF g:V(G)→{-1,0,1}, f≠g, for which g(v)?f(v) for every v∈V(G). The weight of an MTDF is the sum of its function values over all vertices. The minus total domination number of G is the minimum weight of an MTDF on G, while the upper minus domination number of G is the maximum weight of a minimal MTDF on G. In this paper we present upper bounds on the upper minus total domination number of a cubic graph and a 4-regular graph and characterize the regular graphs attaining these upper bounds.     

Characterization of Gromov hyperbolic short graphs

To decide when a graph is Gromov hyperbolic is,in general,a very hard problem.In this paper,we solve this problem for the set of short graphs(in an informal way,a graph G is r-short if the shortcuts in the cycles of G have length less than r):an r-short graph G is hyperbolic if and only if S9r(G)is finite,where SR(G):=sup{L(C):C is an R-isometric cycle in G}and we say that a cycle C is R-isometric if dC(x,y)≤dG(x,y)+R for every x,y∈C.     

Clique graphs of time graphs

A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that v_iv_j ∈ e(G) for v_i ≠ v_j if and only if |f(v_i) ? f(v_j)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K²(G), and inductively, denote K(K^m?1(G)) by K^m(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kⁿ(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived.     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

A method in graph theory

A unified approach to a variety of graph-theoretic problems is introduced. The k-closure C_k(G) of a simple graph G of order n is the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree-sum at least k. It is shown that, for many properties P, one can find a suitable value of k (depending on P and n) such that if C_k(G) has P, then so does G. For instance, if P is the hamiltonian property, one may take k = n. Thus if C_n(G) is hamiltonian, then so is G; in particular, if n ? 3 and C_n(G) is complete, then G is hamiltonian. This condition for a graph to be hamiltonian is shown to imply the well-known conditions of Chvátal and Las Vergnas. The same method, applied to other properties, yields many new theorems of a similar nature.     

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).     

On Integral Sum Graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous relative results are also presented.     

Super edge-magic strength of fire crackers, banana trees and unicyclic graphs

A graph G(V,E) is called super edge-magic if there exists a bijection f from V∪E to {1,2,3,…,|V|+|E|} such that f(u)+f(v)+f(uv)=c(f) is constant for any uv∈E and f(V)={1,2,3,…,|V|}. Such a bijection is called a super edge-magic labeling of G. The super edge-magic strength of a graph G is defined as the minimum of all c(f) where the minimum runs over all super edge-magic labelings of G and is denoted by sm(G). The super edge-magic strength of some families of graphs are obtained in this paper.     

Weak sense of direction labelings and graph embeddings

An edge-labeling λ for a directed graph G has a weak sense of direction (WSD) if there is a function f that satisfies the condition that for any node u and for any two label sequences α and α^′ generated by non-trivial walks on G starting at u, f(α)=f(α^′) if and only if the two walks end at the same node. The function f is referred to as a coding function of λ. The weak sense of direction number of G, WSD(G), is the smallest integer k so that G has a WSD-labeling that uses k labels. It is known that WSD(G)≥Δ⁺(G), where Δ⁺(G) is the maximum outdegree of G.Let us say that a function τ:V(G)→V(H) is an embedding from G onto H if τ demonstrates that G is isomorphic to a subgraph of H. We show that there are deep connections between WSD-labelings and graph embeddings. First, we prove that when f_H is the coding function that naturally accompanies a Cayley graph H and G has a node that can reach every other node in the graph, then G has a WSD-labeling that has f_H as a coding function if and only if G can be embedded onto H. Additionally, we show that the problem “Given G, does G have a WSD-labeling that uses a particular coding function f?” is NP-complete even when G and f are fairly simple.Second, when D is a distributive lattice, H(D) is its Hasse diagram and G(D) is its cover graph, then WSD(H(D))=Δ⁺(H(D))=d^∗, where d^∗ is the smallest integer d so that H(D) can be embedded onto the d-dimensional mesh. Along the way, we also prove that the isometric dimension of G(D) is its diameter, and the lattice dimension of G(D) is Δ⁺(H(D)). Our WSD-labelings are poset-based, making use of Birkhoff’s characterization of distributive lattices and Dilworth’s theorem for posets.     

Binding number and minimum degree for the existence of (g,f,n)-critical graphs

Let G be a graph of order p. The binding number of G is defined as $\mbox{bind}(G):=\min\{\frac{|N_{G}(X)|}{|X|}\mid\emptyset\neq X\subseteq V(G)\,\,\mbox{and}\,\,N_{G}(X)\neq V(G)\}$ . Let g(x) and f(x) be two nonnegative integer-valued functions defined on V(G) with g(x)≤f(x) for any x∈V(G). A graph G is said to be (g,f,n)-critical if G?N has a (g,f)-factor for each N?V(G) with |N|=n. If g(x)≡a and f(x)≡b for all x∈V(G), then a (g,f,n)-critical graph is an (a,b,n)-critical graph. In this paper, several sufficient conditions on binding number and minimum degree for graphs to be (a,b,n)-critical or (g,f,n)-critical are given. Moreover, we show that the results in this paper are best possible in some sense.     

Graham’s pebbling conjecture on products of many cycles

A pebbling move on a connected graph G consists of removing two pebbles from some vertex and adding one pebble to an adjacent vertex. We define f_t(G) as the smallest number such that whenever f_t(G) pebbles are on G, we can move t pebbles to any specified, but arbitrary vertex. Graham conjectured that f₁(G×H)≤f₁(G)f₁(H) for any connected G and H. We define the α-pebbling number α(G) and prove that α(C_pj×?×C_p2×C_p1×G)≤α(C_pj)?α(C_p2)α(C_p1)α(G) when none of the cycles is C₅, and G satisfies one more criterion. We also apply this result with G=C₅×C₅ by showing that C₅×C₅ satisfies Chung’s two-pebbling property, and establishing bounds for f_t(C₅×C₅).     

Cycle-magic graphs

A simple graph G=(V,E) admits a cycle-covering if every edge in E belongs at least to one subgraph of G isomorphic to a given cycle C. Then the graph G is C-magic if there exists a total labelling f:V∪E→{1,2,…,|V|+|E|} such that, for every subgraph H^′=(V^′,E^′) of G isomorphic to C, ∑_v∈V^′f(v)+∑_e∈E^′f(e) is constant. When f(V)={1,…,|V|}, then G is said to be C-supermagic.We study the cyclic-magic and cyclic-supermagic behavior of several classes of connected graphs. We give several families of C_r-magic graphs for each r?3. The results rely on a technique of partitioning sets of integers with special properties.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.