Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.      

Multigraphs with Δ ≥ 3 are Totally-(2Δ−1)-Choosable

The total graph T(G) of a multigraph G has as its vertices the set of edges and vertices of G and has an edge between two vertices if their corresponding elements are either adjacent or incident in G. We show that if G has maximum degree Δ(G), then T(G) is (2Δ(G) − 1)-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for Δ(G) > 3 was , by Borodin et al. When Δ(G) = 4, our algorithm gives a better upper bound. When Δ(G)∈{3,5,6}, our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in linear time (unlike the algorithm of Borodin et al.).     

Star number and star arboricity of a complete multigraph

Let G be a multigraph. The star number s(G) of G is the minimum number of stars needed to decompose the edges of G. The star arboricity sa(G) of G is the minimum number of star forests needed to decompose the edges of G. As usual λK _n denote the λ-fold complete graph on n vertices (i.e., the multigraph on n vertices such that there are λ edges between every pair of vertices). In this paper, we prove that for n ⩾ 2

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K _n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following:

Tighter Bounds on the Size of a Maximum <Emphasis Type="Italic">P</Emphasis><Subscript>3</Subscript>-Matching in a Cubic Graph

We establish that for any connected cubic graph G of order n > 16 the maximum P ₃-matching in G consists of at least vertices.     

Dirac’s Type Sufficient Conditions for Hamiltonicity and Pancyclicity

Let G = (V, E) be a any simple, undirected graph on n ≥ 3 vertices with the degree sequence . We consider the class of graphs satisfying the condition where , is a positive integer. It is known that is hamiltonian if θ ≤ δ. In this paper,

A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x ₁, x ₂, x ₃, x ₄} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian.     

Non-wandering points and the depth for graph maps

Let G be a graph and f:G→G be continuous.Denote by R(f) andΩ(f) the set of recurrent points and the set of non-wandering points of f respectively.LetΩ_0(f) = G andΩ_n(f)=Ω(f|_(Ω_(n-1)(f))) for all n∈N.The minimal m∈NU {∞} such thatΩ_m(f)=Ω_(m 1)(f) is called the depth of f.In this paper,we show thatΩ_2 (f)=(?) and the depth of f is at most 2.Furthermore,we obtain some properties of non-wandering points of f.     

(U(p, q), U(p − 1, q)) is a generalized Gelfand pair

Denote by G = U(p, q) the orthogonal group of the sesqui-linear quadratic form on and let H ₁ = U(p − 1, q) be the stabilizer of the first unit vector e ₁. Let H ₀ = U(1) and set H = H ₀ × H ₁. Define the character χ _l of H by where . Define the anti-involution σ on G by . In this note we show that any distribution T on G satisfying T(h ₁ gh ₂) = χ _l (h ₁ h ₂) T(g) (g ∈ G; h ₁, h ₂ ∈ H) is invariant under the anti-involution σ. This result implies that (G,  H ₁) is a generalized Gelfand pair.      

Mean-value theorems and extensions of the Elliott-Daboussi theorem on additive arithmetic semigroups

We present more general forms of the mean-value theorems established before for multiplicative functions on additive arithmetic semigroups and prove, on the basis of these new theorems, extensions of the Elliott-Daboussi theorem. Let be an additive arithmetic semigroup with a generating set ℘ of primes p. Assume that the number G(m) of elements a in with “degree” ∂(a)=m satisfies

Gauss-Bonnet Formula, Finiteness Condition, and Characterizations of Graphs Embedded in Surfaces

Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature

Measures on Graphs and Groupoid Measures

The main purpose of this paper is to introduce several measures determined by a given finite directed graph. To construct σ-algebras for those measures, we consider several algebraic structures induced by G; (i) the free semigroupoid of the shadowed graph (ii) the graph groupoid of G, (iii) the disgram set and (iv) the reduced diagram set . The graph measures determined by (i) is the energy measure measuing how much energy we spent when we have some movements on G. The graph measures determined by (iii) is the diagram measure measuring how long we moved consequently from the starting positions (which are vertices) of some movements on G. The graph measures and determined by (ii) and (iv) are the (graph) groupoid measure and the (quotient-)groupoid measure, respectively. We show that above graph measurings are invariants on shadowed graphs of finite directed graphs. Also, we will consider the reduced diagram measure theory on graphs. In the final chapter, we will show that if two finite directed graphs G ₁ and G ₂ are graph-isomorphic, then the von Neumann algebras L ^∞(μ ₁) and L ^∞(μ ₂) are *-isomorphic, where μ ₁ and μ ₂ are the same kind of our graph measures of G ₁ and G ₂, respectively. Received: December 7, 2006. Revised: August 3, 2007. Accepted: August 18, 2007.     

Disproof of a Conjecture on the Subdivision Domination Number of a Graph

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sd_γ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.     

A New Bound on the Total Domination Subdivision Number

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that for every simple connected graph G of order n ≥ 3,

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Classification of arithmetically Gorenstein divisors on some Fano varieties

We find all the arithmetically Gorenstein divisors on Fano varieties of dimension n and index r with 3 ≤ n ≤ 2r − 1 and ρ(Y) ≥ 2, where Y is smooth, connected, subcanonical and linearly normal.      

Immersions of spheres and algebraically constructible functions

Let Λ be an algebraic set and let (n is even) be a polynomial mapping such that for each there is r(λ) > 0 such that the mapping g _λ  =  g(· , λ) restricted to the sphere S ⁿ (r) is an immersion for every 0  <  r  <  r (λ), so that the intersection number I(g _λ|S ⁿ (r)) is defined. Then is an algebraically constructible function. I. Karolkiewicz and A. Nowel supported by the grant BW/5100-5-0286-7.     

On Characterizations of Rigid Graphs in the Plane Using Spanning Trees

We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G. A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice.     

Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs

Let G = (V, E) be a connected graph. For a vertex subset , G[S] is the subgraph of G induced by S. A cycle C (a path, respectively) is said to be an induced cycle (path, respectively) if G[V(C)] = C (G[V(P)] = P, respectively). The distance between a vertex x and a subgraph H of G is denoted by , where d(x, y) is the distance between x and y. A subgraph H of G is called 2-dominating if d(x, H) ≤ 2 for all . An induced path P of G is said to be maximal if there is no induced path P′ satisfying and . In this paper, we assume that G is a connected claw-free graph satisfying the following condition: for every maximal induced path P of length p ≥ 2 with end vertices u, v it holds:

Quadratic forms on graphs

We introduce a new graph parameter, called the Grothendieck constant of a graph G=(V,E), which is defined as the least constant K such that for every A:E→ℝ,