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.     

On island sequences of labelings with a condition at distance two

An L(2,1)-labeling of a graph G is a function f from the vertex set of G to the set of nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1, and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between the pair of vertices x,y. The lambda number of G, denoted λ(G), is the minimum range of labels used over all L(2,1)-labelings of G. An L(2,1)-labeling of G which achieves the range λ(G) is referred to as a λ-labeling. A hole of an L(2,1)-labeling is an unused integer within the range of integers used. The hole index of G, denoted ρ(G), is the minimum number of holes taken over all its λ-labelings. An island of a given λ-labeling of G with ρ(G) holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] inquired about the existence of a connected graph G with ρ(G)≥1 possessing two λ-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2.     

Degenerate bifurcation at simple eigenvalues and stability of bifurcating solutions

Let X and Y be Banach spaces, Y ?X, and let V be a neighborhood of zero in Y. We consider the equation G(λ, u) ≡ A(λ)u + F(λ, u) = 0, where G: [?d₁, d₁] × V → X, G(λ, 0) = 0, and A(λ) is the Fréchet derivative of G with respect to u at (λ, 0). Furthermore, we assume that G is analytic with respect to λ and u. Bifurcation at a simple eigenvalue means that zero is a simple eigenvalue of A (0). Let μ(λ) be the simple eigenvalue of the perturbed operator A(λ) for λ near zero. Let $\text{d}{}^{\mathrm{j}}\text{μ(0)}\text{dλ}{}^{\mathrm{j}}\text{= 0, j = 0,…, m ? 1,}\text{d}{}^{\mathrm{m}}\text{μ(0)}\text{dλ}{}^{\mathrm{m}}\text{A}{}_{\mathrm{m}}\text{≠ 0,}\text{or}\text{μ(λ) ≡ 0}$. Under the nondegeneracy condition m = 1 the existence of a unique curve of solutions intersecting the trivial solution (λ, 0) at (0, 0) is well known. Furthermore the “Principle of Exchange of Stability” was established in this case. We show that in the degenerate case (m > 1) up to m bifurcating curves of solutions can exist and that at least one nontrivial curve exists if m is odd. Our approach supplies all curves of solutions near (0, 0) together with their direction of bifurcation and their linearized stability. The decisive fact is that A_m is also the leading term of the bifurcation equation. A consequence is a “Generalized Principle of Exchange of Stability”, which means that adjacent solutions for the same λ have opposite stability properties in a weakened sense. For practical use we give a criterion for asymptotic stability or instability which follows from the construction of the curves of solutions themselves.     

Computability of finite-dimensional linear subspaces and best approximation

We discuss computability properties of the set P_G(x) of elements of best approximation of some point x∈X by elements of G⊆X in computable Banach spaces X. It turns out that for a general closed set G, given by its distance function, we can only obtain negative information about P_G(x) as a closed set. In the case that G is finite-dimensional, one can compute negative information on P_G(x) as a compact set. This implies that one can compute the point in P_G(x) whenever it is uniquely determined. This is also possible for a wider class of subsets G, given that one imposes additionally convexity properties on the space. If the Banach space X is computably uniformly convex and G is convex, then one can compute the uniquely determined point in P_G(x). We also discuss representations of finite-dimensional subspaces of Banach spaces and we show that a basis representation contains the same information as the representation via distance functions enriched by the dimension. Finally, we study computability properties of the dimension and the codimension map and we show that for finite-dimensional spaces X the dimension is computable, given the distance function of the subspace.     

Potential theory associated with Uhlenbeck-Ornstein process

Some parallel results of Gross' paper (Potential theory on Hilbert space, J. Functional Analysis1 (1967), 123–181) are obtained for Uhlenbeck-Ornstein process U(t) in an abstract Wiener space (H, B, i). Generalized number operator $\text{N}$ is defined by $\text{N}$f(x) = ?lim_∈←0{E[f($\text{U}$(τ^∈_ξ))] ? f(x)}/E[τ^∈_ξ, where τ_x^? is the first exit time of U(t) starting at x from the ball of radius ? with center x. It is shown that $\text{N}$f(x) = ?trace D²f(x)+〈Df(x),x〉 for a large class of functions f. Let r_t(x, dy) be the transition probabilities of U(t). The λ-potential G_λf, λ > 0, and normalized potential Rf of f are defined by G_λf(X) = ∫₀^∞e^?λtr_tf(x) dt and Rf(x) = ∫₀^∞ [r_tf(x) ? r_tf(0)] dt. It is shown that if f is a bounded Lip-1 function then trace D²G_λf(x) ? 〈DG_λf(x), x〉 = ?f(x) + λG_λf(x) and trace D²Rf(x) ? 〈DRf(x), x〉 = ?f(x) + ∫_Bf(y)p₁(dy), where p₁ is the Wiener measure in B with parameter 1. Some approximation theorems are also proved.     

On commutation semigroups of dihedral groups

For any group G with g∈G, the right and left commutation semigroups associated with g are the mappings ρ(g) and λ(g) from G to G defined as (x)ρ(g)=[x,g] and (x)λ(g)=[g,x]. The set M(G) of all mappings from G to G forms a semigroup under composition of mappings. The right and left commutation semigroups of G, denoted P(G) and Λ(G), are the subsemigroups of M(G) generated by {ρ(g):g∈G} and {λ(g):g∈G}, respectively. In this paper, we develop explicit formulas for the orders of P(G) and Λ(G) when G=D _m , the dihedral group of order 2m. We apply these formulas to address the problems of determining when |P(G)|=|Λ(G)| and P(G)?Λ(G) and to derive proofs of several previous results of James Countryman (Ph.D. Thesis, University of Notre Dame, 1970) on commutation semigroups of pq groups.     

Polynomials on graphs

Let G be a simple graph with adjacency matrix A, and p(x) a polynomial with rational coefficients. If p(A) is the adjacency matrix of a graph, we denote that graph by p(G). We consider the question: Given a graph G, which polynomials p(x) give rise to a graph p(G) and what are those graphs? We give a complete answer if G is a distance-regular graph. We then derive some general relations between the polynomials p(x), the spectrum of A, and the automorphism group of G.     

On positive solutions of perturbed nonlinear differential equations

Some results are given concerning positive solutions of equations of the form x⁽ⁿ⁾ + P(t) G(x) = Q(t, x).Let class I (II) consist of all n-times differentiable functions x(t), such that x(t)>0 and x^{(n ? 1)}(t) ? 0 (x^{(n ? 1)}(t) ? 0) for all large t. Two theorems are given guaranteeing the nonexistence of solutions in class I and II, respectively, and three theorems ensure the convergence to zero of positive solutions. A recent result of Hammett concerning the second-order case is extended to the general case.     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

A recurrent pattern in the list of quadratic residues mod a prime and in the values of the liouville λ function

Certain patterns of values of totally multiplicative functions are studied. The main theorem is that if λ is totally multiplicative and assumes only the values ±1 then the pattern λ(x) = λ(x ? 1) = λ(x ? 4) = 1 occurs infinitely often. In fact, given S there is a positive B, depending only on S, so that this pattern occurs with S ≤ x ≤ S + B, for every choice of λ.     

A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees

Let G be a connected simple graph, let X?V (^G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d _T (x) for all x ∈ X, where d _T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d _T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N _G (S) ? S| ? f(S) + 2|S| ? ω _G (S) ≥, where ω _G (S) is the number of components of the subgraph induced by S.     

A general class of fuzzy operators,the demorgan class of fuzzy operators and fuzziness measures induced by fuzzy operators

In this paper we examine operators which can be derived from the general solution of functional equations on associativity. We define the characteristics of those functions f(x) which are necessary for the production of operators. We shall show, that with the help of the negation operator for every such function f(x) a function g(x) can be given, from which a disjunctive operator can be derived, and for the three operators the DeMorgan identity is fulfilled. For the fulfillment of the DeMorgan identity the necessary and sufficient conditions are given.We shall also show that an f_λ(x) can be constructed for every f(x), so that for the derived k_λ(x,y) and d_λ(x,y) lim_λ→∞k_λ(x,y) and lim_λ→∞d_λ(x,y) = max(x,y).As Yager's operator is not reducible, for every λ there exists an α, for which, in case x < α and y<α, k_λ(x,y) = 0.We shall give an f(x) which has the characteristics of Yager's operator, and which is strictly monotone.Finally we shall show, that with the help of all those f(x), which are necessary when constructing a k(x,y), an F(x) can be constructed which has the properties of the measures of fuzziness introduced by A. De Luca and S. Termini. Some classical fuzziness measures are obtained as special cases of our system.     

Invariant subspaces of analytic multiparticle Hamiltonians

The quantum mechanics of n particles interacting through analytic two-body interactions can be formulated as a problem of functional analysis on a Hilbert space $\text{G}$ consisting of analytic functions. On $\text{G}$, there is an Hamiltonian H with resolvent R(λ). These quantities are associated with families of operators H(?) and R(λ, ?) on $\text{L}$, the case ? = 0 corresponding to standard quantum mechanics. The spectrum of H(?) consists of possible isolated points, plus a number of half-lines starting at the thresholds of scattering channels and making an angle 2? with the real axis.Assuming that the two-body interactions are in the Schmidt class on the two-particle space $\text{G}$, this paper studies the resolvent R(λ, ?) in the case ? ≠ 0. It is shown that a well known Fredholm equation for R(λ, ?) can be solved by the Neumann series whenever ¦λ¦ is sufficiently large and λ is not on a singular half-line. Owing to this, R(λ, ?) can be integrated around the various half-lines to yield bounded idempotent operators P_p(?) (p = 1, 2,…) on $\text{L}$. The range of P_p(?) is an invariant subspace of H(?). As ? varies, the family of operators P_p(?) generates a bounded idempotent operator P_p on a space $\text{G}$. The range of this is an invariant subspace of H. The relevance of this result to the problem of asymptotic completeness is indicated.     

On spectral characterizations and embeddings of graphs

The least eigenvalue of the 0-1 adjacency matrix of a graph is denoted λ G. In this paper all graphs with λ(G) greater than ?2 are characterized. Such a graph is a generalized line graph of the form L(T;1,0,…,0), L(T), L(H), where T is a tree and H is unicyclic with an odd cycle, or is one of 573 graphs that arise from the root system E₈. If G is regular with λ(G)>?2, then Gis a clique or an odd circuit. These characterizations are used for embedding problems; λ_R(H) = sup{λ(G)z.sfnc;HinG; Gregular}. H is an odd circuit, a path, or a complete graph iff λ_R(H)> ?2. For any other line graph H, λ_R(H) = ?2. A similar result holds for complete multipartite graphs.     

Distance matrix polynomials of trees

Let G be a finite connected graph. If x and y are vertices of G, one may define a distance function d_G on G by letting d_G(x, y) be the minimal length of any path between x and y in G (with d_G(x, x) = 0). Thus, for example, d_G(x, y) = 1 if and only if {x, y} is an edge of G. Furthermore, we define the distance matrix D(G) for G to be the square matrix with rows and columns indexed by the vertex set of G which has d_G(x, y) as its (x, y) entry. In this paper we are concerned with properties of D(G) for the case in which G is a tree (i.e., G is acyclic). In particular, we precisely determine the coefficients of the characteristic polynomial of D(G). This determination is made by deriving surprisingly simple expressions for these coefficients as certain fixed linear combinations of the numbers of various subgraphs of G.     

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.     

Global branches of periodic solutions for forced delay differential equations on compact manifolds

We prove a global bifurcation result for T-periodic solutions of the T-periodic delay differential equation x^′(t)=λf(t,x(t),x(t−1)) depending on a real parameter λ?0. The approach is based on the fixed point index theory for maps on ANRs.     

On the spectral radius of ‡-shape trees

Let A(G) be the adjacency matrix of G. The characteristic polynomial of the adjacency matrix A is called the characteristic polynomial of the graph G and is denoted by φ(G, λ) or simply φ(G). The spectrum of G consists of the roots (together with their multiplicities) λ ₁(G) ? λ ₂(G) ? … ? λ _n (G) of the equation φ(G, λ) = 0. The largest root λ ₁(G) is referred to as the spectral radius of G. A ?-shape is a tree with exactly two of its vertices having maximal degree 4. We will denote by G(l ₁, l ₂, … l ₇) (l ₁ ? 0, l _i ? 1, i = 2, 3, …, 7) a ?-shape tree such that $G\left( {l_1 ,l_2 , \ldots l_7 } \right) - u - v = P_{l_1 } \cup P_{l_2 } \cup \ldots P_{l_7 }$ , where u and v are the vertices of degree 4. In this paper we prove that ${{3\sqrt 2 } \mathord{\left/ {\vphantom {{3\sqrt 2 } 2}} \right. \kern-0em} 2} < \lambda _1 \left( {G\left( {l_1 ,l_2 , \ldots l_7 } \right)} \right) < {5 \mathord{\left/ {\vphantom {5 2}} \right. \kern-0em} 2}$ .     

Spectral properties of the neutron transport equation

The general equation describing the steady-state flow through a porous column is λu ? D_xA(D_x?(u) + G(u)) = f, where λ is a nonnegative constant. In this paper existence, uniqueness and comparison results for solutions to the Dirichlet and mixed boundary value problems associated with this equation are proven. The existence of a weak solution to the evolution problems associated with the equation u_t = D_x(D_x?(u) + G(u)) are deduced.     

The chromatic polynomial of an unlabeled graph

We investigate the chromatic polynomial χ(G, λ) of an unlabeled graph G. It is shown that $\text{χ(G, λ) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{χ(g, π, λ)}$, where g is any labeled version of G, A(g) is the automorphism group of g and χ(g, π, λ) is the chromatic polynomial for colorings of g fixed by π. The above expression shows that χ(G, λ) is a rational polynomial of degree n = |V(G)| with leading coefficient $\text{1}\text{|A(g)|}$. Though χ(G, λ) does not satisfy chromatic reduction, each polynomial χ(g, π, λ) does, thus yielding a simple method for computing χ(G, λ). We also show that the number N(G) of acyclic orientations of G is related to the argument λ = ?1 by the formula $\text{N(G) = (}\text{1}\text{|A(g)|}\text{) Σ}{}_{\mathrm{\pi \; \in \; A(g)}}\text{(?1)}{}^{\mathrm{s(\pi )}}\text{χ(g, π, ?1)}$, where s(π) is the number of cycles of π. This information is used to derive Robinson's (“Combinatorial Mathematics V” (Proc. 5th Austral. Conf. 1976), Lecture Notes in Math. Vol. 622, pp. 28–43, Springer-Verlag, New York/Berlin, 1977) cycle index sum equations for counting unlabeled acyclic digraphs.