On double bound graphs and forbidden subposets

For a poset P=(X,≤_P), the double bound graph (DB-graph) of P is the graph DB(P)=(X,E_DB(P)), where xy∈E_DB(P) if and only if x≠y and there exist n,m∈X such that n≤_Px,y≤_Pm. We obtain that for a subposet Q of a poset P,Q is an (n, m)-subposet of P if and only if DB(Q) is an induced subgraph DB(P). Using this result, we show some characterizations of split double bound graphs, threshold double bound graphs and difference double bound graphs in terms of (n, m)-subposets and double canonical posets.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On the complexity of paths avoiding forbidden pairs

Given a graph G=(V,E), two fixed vertices s,t∈V and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.We write x?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)∈F we have x?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)∈F satisfy v?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)∈F satisfy u?x?v?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

Competitively Tight Graphs

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ _E (G) of the graph G via θ _E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ _E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ _E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ _E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ _E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

A nonlinear evolution system with two subdifferentials and monotone differential games

It is shown that the first order multivalued equation for V = V(t, x, y, z) involving the sum of two subdifferentials composed with the partials of V (V_t +f(t, x, y, z) · ▽_xV + β(V_y) + γ(V_z) + h(t, x, y, z) ? 0 a.e.) has a Lipschitz solution. This solution is shown to be the value of a differential game in which the players are restricted to choosing monotone nondecreasing functions of time. Accordingly, the multivalued equation is interpreted as the corresponding Hamilton-Jacobi equation of the game.     

Characterization of projective graphs

We denote the distance between vertices x and y of a graph by d(x, y), and p_ij(x, y) = ∥ {z : d(x, z) = i, d(y, z) = j} ∥. The (s, q, d)-projective graph is the graph having the s-dimensional subspaces of a d-dimensional vector space over GF(q) as vertex set, and two vertices x, y adjacent iff $\text{dim}\text{(x ? y) = s ? 1}$. These graphs are regular graphs. Also, there exist integers λ and μ > 4 so that μ is a perfect square, p₁₁(x, y) = λ whenever d(x, y) = 1, and p₁₁(x, y) = μ whenever d(x, y) = 2. The (s, q, d)-projective graphs where $\text{2d}\text{3}\text{≤ s < d ? 2}$ and $\text{(s, q, d) ≠ (}\text{2d}\text{3}\text{, 2, d)}$, are characterized by the above conditions together with the property that there exists an integer r satisfying certain inequalities.     

Small-amplitude limit cycles of polynomial Liénard systems

In this paper,we study the number of limit cycles appeared in Hopf bifurcations of a Linard system with multiple parameters.As an application to some polynomial Li’enard systems of the form x=y,y=gm(x)-fn(x)y,we obtain a new lower bound of maximal number of limit cycles which appear in Hopf bifurcation for arbitrary degrees m and n.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

Strong edge-magic graphs of maximum size

An edge-magic total labeling on G is a one-to-one map λ from V(G)∪E(G) onto the integers 1,2,…,|V(G)∪E(G)| with the property that, given any edge (x,y), λ(x)+λ(x,y)+λ(y)=k for some constant k. The labeling is strong if all the smallest labels are assigned to the vertices. Enomoto et al. proved that a graph admitting a strong labeling can have at most 2|V(G)|-3 edges. In this paper we study graphs of this maximum size.     

A note on Z 3-connected graphs with degree sum condition

A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al.     

Strict Betweennesses Induced by Posets as well as by Graphs

For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V ³ such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let B_s(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V ³ such that y is an internal vertex on an induced path in G between x and z. The ternary relations B_s(P){\cal B}_s(P) and B_s(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation B_s(P)=B_s(G){\cal B}_s(P)={\cal B}_s(G).     

A variational approach to dislocation problems for periodic Schrödinger operators

As a simple model for lattice defects like grain boundaries in solid state physics we consider potentials which are obtained from a periodic potential V=V(x,y) on R² with period lattice Z² by setting Wt(x,y)=V(x+t,y) for x<0 and Wt(x,y)=V(x,y) for x?0, for t∈[0,1]. For Lipschitz-continuous V it is shown that the Schrödinger operators Ht=−Δ+Wt have spectrum (surface states) in the spectral gaps of H₀, for suitable t∈(0,1). We also discuss the density of these surface states as compared to the density of the bulk. Our approach is variational and it is first applied to the well-known dislocation problem (Korotyaev (2000, 2005) [15] and [16]) on the real line. We then proceed to the dislocation problem for an infinite strip and for the plane. In Appendix A, we discuss regularity properties of the eigenvalue branches in the one-dimensional dislocation problem for suitable classes of potentials.     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

Path extendability of claw-free graphs

Let G be a connected, locally connected, claw-free graph of order n and x,y be two vertices of G. In this paper, we prove that if for any 2-cut S of G, S∩{x,y}=∅, then each (x,y)-path of length less than n-1 in G is extendable, that is, for any path P joining x and y of length h(<n-1), there exists a path P^′ in G joining x and y such that V(P)⊂V(P^′) and |P^′|=h+1. This generalizes several related results known before.     

A lower bound for the circumference of a graph

Let G=(V, E) be a block of order n, different from K_n. Let m=min {d(x)+d(y): [x, y]?E}. We show that if m?n then G contains a cycle of length at least m.     

Identifying codes and locating-dominating sets on paths and cycles

Let G=(V,E) be a graph and let r≥1 be an integer. For a set D⊆V, define N_r[x]={y∈V:d(x,y)≤r} and D_r(x)=N_r[x]∩D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating-dominating set, respectively), if for all vertices x∈V (x∈V?D, respectively), D_r(x) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72-82] provided complete results for the paths and cycles when r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for r-identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969-987].     

Recurrent points and non-wandering points of graph maps

Let G be a graph and f:G→G be a continuous map. Denote by P(f), R(f) and Ω(f) the sets of periodic points, recurrent points and non-wandering points of f, respectively. In this paper we show that: (1) If L=(x,y) is an open arc contained in an edge of G such that {fm(x),fk(y)}⊂(x,y) for some m,k∈N, then R(f)∩(x,y)≠∅; (2) Any isolated point of P(f) is also an isolated point of Ω(f); (3) If x∈Ω(f)−Ω(fn) for some n∈N, then x is an eventually periodic point. These generalize the corresponding results in W. Huang and X. Ye (2001) [9] and J. Xiong (1983, 1986) [17] and [19] on interval maps or tree maps.