A Magnetic Procedure for the Stability Number

A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new vertex linked to all common neighbours of u and v without changing the stability number. We prove that all graphs containing no chordless cycle C _k (k ≥ 5) and none of eleven forbidden subgraphs can be reduced to a stable set by repeated use of magnets. For such graphs a polynomial algorithm is given to determine the stability number.     

On induced subgraphs of a block

If G is a block, then a vertex u of G is called critical if G - u is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each edge is incident with at least one critical vertex and b) each vertex of degree two is critical. Let G be a semicritical block with at least six vertices. It is proved that A) there exist distinct vertices u₂, v₁, u₂, and v₂ of degree two in G such that u₁v₁ and u₂v₂ are edges of G, and u₁v₂, and u₂v₂ are edges of the complement of G, and B) the complement of G is a block with no critical vertex of degree two.     

Properties of almost all graphs and complexes

There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first-order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph (u₁, …, u_n, v₁, …, v_n), there exists another vertex w adjacent to each u₁ and not adjacent to any v_i. A simple counting argument proves that for each n, almost all graphs satisfy Axiom n. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H, almost all graphs have an induced subgraph isomorphic to H. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial complexes.     

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

Distance-transitive graphs admit semiregular automorphisms

A distance-transitive graph is a graph in which for every two ordered pairs of vertices (u,v) and (u^′,v^′) such that the distance between u and v is equal to the distance between u^′ and v^′ there exists an automorphism of the graph mapping u to u^′ and v to v^′. A semiregular element of a permutation group is a non-identity element having all cycles of equal length in its cycle decomposition. It is shown that every distance-transitive graph admits a semiregular automorphism.     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs. Received: October, 2001 Final version received: September 20, 2002 Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor     

Octahedral designs

An oriented octahedral design of order v, or OCT(v), is a decomposition of all oriented triples on v points into oriented octahedra. Hanani [H. Hanani, Decomposition of hypergraphs into octahedra, Second International Conference on Combinatorial Mathematics (New York, 1978), Annals of the New York Academy of Sciences, 319, New York Academy of Science, New York, 1979, pp. 260–264.] settled the existence of these designs in the unoriented case. We show that an OCT(v) exists if and only if v≡1, 2, 6 (mod 8) (the admissible numbers), and moreover the constructed OCT(v) are unsplit, i.e. their octahedra cannot be paired into mirror images. We show that an OCT(v) with a subdesign OCT(U) exists if and only if v and u are admissible and v≥u+4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:319–327, 2010     

Giant components in Kronecker graphs

Let \begin{align*}n\in\mathbb{N}\end{align*}, 0 <α,β,γ< 1. Define the random Kronecker graph K(n,α,γ,β) to be the graph with vertex set \begin{align*}\mathbb{Z}_2^n\end{align*}, where the probability that u is adjacent to v is given by p_u,v =α ^{u ? v} γ^{( 1‐u )?( 1‐v )}β^{n‐ u ? v ‐( 1‐u )?( 1‐v )}. This model has been shown to obey several useful properties of real‐world networks. We establish the asymptotic size of the giant component in the random Kronecker graph.© 2011 Wiley Periodicals, Inc. Random Struct. Alg.,2011     

Hamiltonicity of 3-Arc Graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.     

On local connectivity of graphs with given clique number

For a vertex v of a graph G, we denote by d(v) the degree of v. The local connectivity κ(u, v) of two vertices u and v in a graph G is the maximum number of internally disjoint u –v paths in G, and the connectivity of G is defined as κ(G)=min{κ(u, v)|u, v∈V(G)}. Clearly, κ(u, v)?min{d(u), d(v)} for all pairs u and v of vertices in G. Let δ(G) be the minimum degree of G. We call a graph G maximally connected when κ(G)=δ(G) and maximally local connected when for all pairs u and v of distinct vertices in G. In 2006, Hellwig and Volkmann (J Graph Theory 52 (2006), 7–14) proved that a connected graph G with given clique number ω(G)?p of order n(G) is maximally connected when As an extension of this result, we will show in this work that these conditions even guarantee that G is maximally local connected. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 192–197, 2010     

Fourth-order finite difference method for 2D parabolic partial differential equations with nonlinear first-derivative terms

We attempt to obtain a two-level implicit finite difference scheme using nine spatial grid points of O(k² + kh² + h⁴) for solving the 2D nonlinear parabolic partial differential equation v₁u_xx + v₂u_yy = f(x, y, t, u, u_x, u_y, u₁) where v₁ and v₂ are positive constants, with Dirichlet boundary conditions. The method, when applied to a linear diffusion-convection problem, is shown to be unconditionally stable. Computational efficiency and the results of numerical experiments are discussed.     

The weak density of properly d-r.e. branching degree in the d-r.e. degrees

It is proved that for any r.e. degreesv <u, there exists a properly d-r.e. degreec such thatc is a branching degree andv <c <u. Project supported by the National Natural Science Foundation of China (Grant No. 19771045) and National 863 Hi-Tech R&D Programme.     

The effects of distance and neighborhood union conditions on hamiltonian properties in graphs

We prove that a 2-connected graph G of order p is hamiltonian if for all distinct vertices u and v, dist(u,v) = 2 implies that |N(u) U N(v)| ? (2p - 1)/3. We also demonstrate hamiltonian-connected and traceability properties in graphs under similar conditions.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

Cyclic orthogonal double covers of 4-regular circulant graphs

An orthogonal double cover (ODC) of a graph H is a collection G={G_v:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members G_u and G_v in G, |E(G_u)∩E(G_v)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs.     

On double and multiple interval graphs

In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f(u) of the real line so that f(u) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f(u) and f(v)meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph K_{m, n} has interval number ?(mn + 1)/(m + n)?.     

Autotopisms and Isotopisms of Trilinear Alternating Forms

For a trilinear alternating form f on a vector space V, a generalization of the group of automorphisms group of autotopisms Atp(f), is introduced. An autotopism of f is a triple (α, β, γ) of automorphisms of V satisfying f(u, v, w) = f(α(u), β(v), γ(w)) for all u, v, w ∈ V. Basic results concerning this group are presented, and it is shown that the subgroup of Atp(f) containing autotopisms with identity in one coordinate is Abelian and that a mapping in this group has no fixed points if and only if its order is not a power of two.

Moreover, the notion of equivalence of two trilinear alternating forms is generalized in a similar way, and a partial result is given.

Examples of forms with both trivial (Atp(f) = Aut(f)) and nontrivial groups of autotopisms are presented.     

Quasi‐embeddings of Steiner triple systems,or Steiner triple systems of different orders with maximum intersection

In this paper, we present a conjecture that is a common generalization of the Doyen–Wilson Theorem and Lindner and Rosa's intersection theorem for Steiner triple systems. Given u, v ≡ 1,3 (mod 6), u < v < 2u + 1, we ask for the minimum r such that there exists a Steiner triple system such that some partial system can be completed to an STS , where |?| = r. In other words, in order to “quasi‐embed” an STS(u) into an STS(v), we must remove r blocks from the small system, and this r is the least such with this property. One can also view the quantity (u(u ? 1)/6) ? r as the maximum intersection of an STS(u) and an STS(v) with u < v. We conjecture that the necessary minimum r = (v ? u) (2u + 1 ? v)/6 can be achieved, except when u = 6t + 1 and v = 6t + 3, in which case it is r = 3t for t ≠ 2, or r = 7 when t = 2. Using small examples and recursion, we solve the cases v ? u = 2 and 4, asymptotically solve the cases v ? u = 6, 8, and 10, and further show for given v ? u > 2 that an asymptotic solution exists if solutions exist for a run of consecutive values of u (whose required length is no more than v ? u). Some results are obtained for v close to 2u + 1 as well. The cases where ≈ 3u/2 seem to be the hardest. © 2004 Wiley Periodicals, Inc.     

Triangle path transit functions, betweenness and pseudo-modular graphs

The geodesic and induced path transit functions are the two well-studied interval functions in graphs. Two important transit functions related to the geodesic and induced path functions are the triangle path transit functions which consist of all vertices on all u,v-shortest (induced) paths or all vertices adjacent to two adjacent vertices on all u,v-shortest (induced) paths, for any two vertices u and v in a connected graph G. In this paper we study the two triangle path transit functions, namely the I^Δ and J^Δ on G. We discuss the betweenness axioms, for both triangle path transit functions. Also we present a characterization of pseudo-modular graphs using the transit function I^Δ by forbidden subgraphs.