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

A characterization of robert's inequality for boxicity

F.S. Roberts defined the boxicity of a graph G as the smallest positive integer n for which there exists a function F assigning to each vertex x?G a sequence F(x)(1),F(x)(2),…, F(x)(n) of closed intervals of R so that distinct vertices x and y are adjacent in G if and only if F(x)(i)∩F(y)(i)≠? fori = 1, 2, 3, …, n. Roberts then proved that if G is a graph having 2n + 1 vertices, thentheboxicityofGisatmostn. In this paper, we provide an explicit characterization of this inequality by determining for each n ? 1 the minimum collection $\text{C}$_n of graphs so that a graph G having 2n + 1 vertices has boxicity n if and only if it contains a graph from $\text{C}$_n as an induced subgraph. We also discuss combinatorial connections with analogous characterization problems for rectangle graphs, circular arc graphs, and partially ordered sets.     

Equivalence of measures for some class of Gaussian random fields

We consider two Gaussian measures P₁ and P₂ on (C(G), $\text{B}$) with zero expectations and covariance functions R₁(x, y) and R₂(x, y) respectively, where R_ν(x, y) is the Green's function of the Dirichlet problem for some uniformly strongly elliptic differential operator A^(ν) of order $\text{2m, m ≥ [}\text{d}\text{2}\text{] + 1}$, on a bounded domain G in $\text{R}$^d (ν = 1, 2). It is shown that if the order of A⁽²⁾ ? A⁽¹⁾ is at most $\text{2m ? [}\text{d}\text{2}\text{] ? 1}$, then P₁ and P₂ are equivalent, while if the order is greater than $\text{2m ? [}\text{d}\text{2}\text{] ? 1}$, then P₁ and P₂ are not always equivalent.     

A conjecture of Kippenhahn about the characteristic polynomial of a pencil generated by two Hermitian matrices. II

Let A be an n × n matrix; write A = H+iK, where i²=—1 and H and K are Hermitian. Let f(x,y,z) = det(zI?xH?yK). We first show that a pair of matrices over an algebraically closed field, which satisfy quadratic polynomials, can be put into block, upper triangular form, with diagonal blocks of size 1×1 or 2×2, via a simultaneous similarity. This is used to prove that if $\text{f(x,y,z) = [g(x,y,z)]}{}^{\mathrm{<mtext>n</mtext><mtext>2</mtext>}}$, where g has degree 2, then for some unitary matrix U, the matrix U¹AU is the direct sum of $\text{n}\text{2}$ copies of a 2×2 matrix A₁, where A₁ is determined, up to unitary similarity, by the polynomial g(x,y,z). We use the connection between f(x,y,z) and the numerical range of A to investigate the case where f(x,y,z) has the form (z?αax? βy)^r[g(x,y,z)]^s, where g(x,y,z) is irreducible of degree 2.     

Bounding the diameter of a distance-transitive graph

A graph Γ is distance-transitive if for all vertices u, v, x, y such that d(u, v) = d(x, y) there is an automorphism h of Γ such that uh = x, vh = y. We show how to find a bound for the diameter of a bipartite distance-transitive graph given a bound for the order |G_α| of the stabilizer of a vertex.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Boolean distance for graphs

The boolean distance between two points x and y of a connected graph G is defined as the set of all points on all paths joining x and y in G (Ø if x = y). It is determined in terms of the block-cutpoint graph of G, and shown to satisfy the triangle inequality b(x,y)? b(x, z)∪b(z,y). We denote by B(G) the collection of distinct boolean distances of G and by M(G) the multiset of the distances together with the number of occurrences of each of them. Then $\text{B(G)}\text{= 1+(}{}^{\mathrm{b+1}}{}_2\text{)}$ where b is the number of blocks of G. A combinatorial characterization is given for B(T) where T is a tree. Finally, G is reconstructible from M(G) if and only if every block of G is a line or a triangle.     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

On complementary graphs with no isolated vertices

Let $\text{G}$ denote the complement of a graph G, and x(G), β₁(G), β₄(G), α₀(G), α₁(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order $\text{p}\text{, {2√p} ? x(G) + x(}\text{G}\text{) ? p + 1}\text{and p}\text{? x(G)·x(}\text{G}\text{) ? [(}\text{1}\text{2}\text{(p + 1))}{}^2\text{]}$. Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β₁(G) + α₁(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of $\text{G}\text{and}\text{G}$, since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both $\text{G}\text{and}\text{G}$ contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G.     

Isometric cycles,cutsets, and crowning of bridged graphs

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d_G(x,y) < d_C(x,y). A cycle C is isometric if d_G(x,y) = d_C(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d_G(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003     

Arithmetic in generalized Artin-Schreier extensions of k(x)

If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions K_n over k(x) such that [K : k(x)] = pⁿ using the concept of Witt vectors. This is accomplished in the following way; if [β₁, β₂,…, β_n] is a Witt vector over k(x) = K₀, then the Witt equation $\text{y}{}^{\mathrm{p}}\text{?}\text{y}\text{= β}$ generates a tower of extensions through $\text{K}{}_{\mathrm{i}}\text{= K}{}_{\mathrm{i?1}}\text{(}\text{y}{}_{\mathrm{i}}\text{)}$ where $\text{y}\text{= [}\text{y}{}_1\text{,}\text{y}{}_2\text{,…,}\text{y}{}_{\mathrm{n}}\text{]}$. In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in K_n. This alternate generation has the form K_i = K_i?1(y_i); y_i^p ? y_i = B_i, where, as a divisor in K_i?1, B_i has the form . In this form q is prime to Πp_j^λ_j and each λ_j is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field K_n over an algebraically closed field of constants.     

Regular graphs with high edge degree

For any vertex x of a graph G let Δ(x) denote the set of vertices adjacent to x. We seek to describe the connected graphs G which are regular of valence n and in which for all adjacent vertices x and y |Δ(x) ∩ Δ(y)| = n ? 1 ? s. It is known that the complete graphs are the graphs for which s = 0. For any s, any complete many-partite graph, each part containing s + 1 vertices, is such a graph. We show that these are the only such graphs for which the valence exceeds 2s² ? s + 1. The graphs satisfying these conditions for s = 1 or 2 are characterized (up to the class of trivalent triangle-free graphs.)     

Subsequent to a theorem of Markoff

Let f(x, y) be an indefinite binary quadratic form, d(f) its discriminant, m(f) the infimum of |f(x, y)| over all integers x, y not both zero, and put $\text{μ(f) = m(f)d(f)}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$. In this paper we prove the existence of countably many disjoint open intervals I_j contained in $\text{0 ≤ x ≤}\text{1}\text{3}$ such that there is no f with μ(f) in I_j (j = 1, 2,…) and such that for any interval I containing two intervals I_j, I_k there is an f with μ(f) in I.     

A nonlinear three-point boundary value problem

We consider the differential equation ?(py′)′ + qy + λay + μby + f(x, y, y′) = 0, x? (α, γ) subject to the boundary conditions cos(α₁) y(α) ? sin(α₁) y′(α) = 0cos(β₁) y(β) ? sin(β₁) y′(β) = 0 β? (α, γ)cos(γ₁) y(γ) ? sin(γ₁) y′(γ) = 0. The functions p, g, a, b, and f are well-behaved functions of x; f is smooth and of “higher order” in y and y′; the scalars λ and μ are eigenparameters. With mild restrictions on a and b it is known that the linearized problem, f ≡ 0, has eigensolutions, ($\text{λ}{}^1\text{, μ}{}^1\text{, ψ}{}^1$). In this paper we use an Implicit Function Theorem argument to establish the existence of a local branch of solutions, bifurcating from ($\text{λ}{}^1\text{, μ}{}^1\text{, 0}$), to the above nonlinear two-parameter eigenvalue problem.     

Induced path transit function, monotone and Peano axioms

The induced path transit function J(u,v) in a graph consists of the set of all vertices lying on any induced path between the vertices u and v. A transit function J satisfies monotone axiom if x,y∈J(u,v) implies J(x,y)⊆J(u,v). A transit function J is said to satisfy the Peano axiom if, for any u,v,w∈V,x∈J(v,w), y∈J(u,x), there is a z∈J(u,v) such that y∈J(w,z). These two axioms are equivalent for the induced path transit function of a graph. Planar graphs for which the induced path transit function satisfies the monotone axiom are characterized by forbidden induced subgraphs.     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

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.     

Oscillatory and asymptotic behavior of solutions of differential equations with deviating arguments

The oscillatory and asymptotic behavior of solutions of a class of nth order nonlinear differential equations, with deviating arguments, of the form (E, δ) L_nx(t) + δq(t) f(x[g₁(t)],…, x[g_m(t)]) = 0, where δ = ± 1 and L₀x(t) = x(t), L_kx(t) = a_k(t)(L_{k ? 1}x(t))^., $\text{k = 1, 2,…, n (}{}^{\mathrm{.}}\text{=}\text{d}\text{dt}\text{)}$, is examined. A classification of solutions of (E, δ) with respect to their behavior as t → ∞ and their oscillatory character is obtained. The comparisons of (E, 1) and (E, ?1) with first and second order equations of the form y^.(t) + c₁(t) f(y[g₁(t)],…, y[g_m(t)]) = 0 and (a_{n ? 1}(t)z^.(t))^. ? c₂(t) f(z[g₁(t)],…, z[g_m(t)]) = 0, respectively, are presented. The obtained results unify, extend and improve some of the results by Graef, Grammatikopoulos and Spikes, Philos and Staikos.     

Degree sum and nowhere-zero 3-flows

Let G be a simple graph on n vertices. In this paper, we prove that if G satisfies the condition that d(x)+d(y)≥n for each xy∈E(G), then G has no nowhere-zero 3-flow if and only if G is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices.