Path covers of weighted graphs

Let (G, w) denote a simple graph G with a weight function w : E(G) ← {0, 1, 2}. A path cover of (G, w) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex v, w(v) is the sum of the weights of the edges incident with v; v is called an odd (even) vertex if w(v) is odd (even). We prove that if every vertex of (G, w) is incident with at most one edge of weight 2, then (G, w) has a path cover P such that each odd vertex occurs exactly once, and each even vertex exactly twice, as an end of a path of P. We also prove that if every vertex of (G, w) is even, then (G, w) has a path cover P such that each vertex occurs exactly twice as an end of a path of P. © 1995 John Wiley & Sons, Inc.     

Directed Graph Pattern Matching and Topological Embedding

Pattern matching in directed graphs is a natural extension of pattern matching in trees and has many applications to different areas. In this paper, we study several pattern matching problems in ordered labeled directed graphs. For the rooted directed graph pattern matching problem, we present an efficient algorithm which, given a pattern graphPand a target graphT, runs in time and spaceO(|E_P| |V_T| + |E_T|). It is faster than the best known method by a factor ofmin{|E_T|, |E_P| |V_T|}. This algorithm can also solve the directed graph pattern matching problem without increasing time or space complexity. Our solution to this problem outperforms the best existing method by Katzenelson, Pinter and Schenfeld by a factor ofmin{|V_P| |E_T|, |V_P| |E_P| |V_T|}. We also present an algorithm for the directed graph topological embedding problem which runs in timeO(|V_P| |E_T| + |E_P|) and spaceO(|V_P| |V_T| + |E_P| + |E_T|). To our knowledge, this algorithm is the first one for this problem.     

Embedding height balanced trees and Fibonacci trees in hypercubes

A height balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the difference b _T (v) between the heights of the subtrees, rooted at the left and right child of v is at most one. We show that a height-balanced tree T _h of height h is a subtree of the hypercube Q _h+1 of dimension h+1, if T _h contains a path P from its root to a leaf such that $\mathbf{b}_{T_{h}}(v)=1$ , for every non-leaf vertex v in P. A Fibonacci tree $\mathbb{F}_{h}$ is a height balanced tree T _h of height h in which $\mathbf{b}_{\mathbb{F}_{h}}(v)=1$ , for every non-leaf vertex. $\mathbb{F}_{h}$ has f(h+2)?1 vertices where f(h+2) denotes the (h+2)th Fibonacci number. Since f(h)～2^0.694h , it follows that if $\mathbb{F}_{h}$ is a subtree of Q _n , then n is at least 0.694(h+2). We prove that $\mathbb{F}_{h}$ is a subtree of the hypercube of dimension approximately 0.75h.     

Graph Orientations with Edge-connection and Parity Constraints

Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed. The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge-connected graph with |V| + |E| even has a (k-1)-edge-connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will be given for digraphs with a root-node s having k edge-disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s. Received December 14, 1998/Revised January 12, 2001 RID="*" ID="*" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772. Part of research was done while this author was visiting EPFL, Lausanne, June, 1998. RID="†" ID="†" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772 and OTKA T030059.     

Existence of directed triplewhist tournaments with the three person property

A directed triplewhist tournament on v players, briefly DTWh(v), is said to have the three person property if no two games in the tournament have three common players. We briefly denote such a design as a 3PDTWh(v). In this paper, we show that a 3PDTWh(v) exists whenever v>17 and with few possible exceptions.     

On the Polar Decomposition of the Product of Two Operators and Its Applications

Let T = U|T| and S = V|S| be the polar decompositions. In this paper, we shall obtain the polar decomposition of TS as TS = UWV|TS|, where |T||S^*| = W||T||S^*|| is the polar decomposition. Next, we shall show that TS = UV|TS| is the polar decomposition if and only if |T| commutes with |S^*|. Lastly, we shall apply this result to binormal and centered operators. We shall obtain characterizations of these operator classes from the viewpoint of the polar decomposition.     

-Decompositions of and D v ∪P where P is a 2-Regular Subgraph of D v

In this paper, we extend the study of C₄-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D_v, then and D_v∪P can be decomposed into directed 4-cycles, respectively, if and only if v(v−1)−|E(P)|≡0(mod 4) and v(v−1)+|E(P)|≡0(mod 4) where |E(P)| denotes the number of directed edges of P, and v≥8.     

Table algebras with multiple P-polynomial structures

Using covering numbers we prove that a standard real integral table algebra (A, B) with |B| ≥ 6 has a P-polynomial structure with respect to every b ≠ 1 in B if and only if 2|B|-1 is prime and (A, B) is exactly isomorphic to the Bose-Mesner algebra of the association scheme of the ordinary (2|B|-1)-gon. Then we present an example showing that this result is not true if |B| ≤ 5.     

Hamiltonian graphs involving distances

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3K_n/3 U T₁ U T₂, where n ? O (mod 3), and T₁ and T₂ are the edge sets of two vertex disjoint triangles containing exactly one vertex from each K_n/3. This result generalizes both Fan's and Lindquester's results as well as several others.     

3-connected graphs with non-cut contractible edge covers of size k

In this paper, we show that if a 3-connected graph G other than K₄ has a vertex subset K that covers the set of contractible edges of G and if |K| 3 and |V(G)| 3|K| ? 1, then K is a cutset of G. We also give examples to show that this result is best possible. In particular, the result does not hold for K with smaller cardinality.     

Semisummands and semiideals in banach spaces

Let |·| be a fixed absolute norm onR ². We introduce semi-|·|-summands (resp. |·|-summands) as a natural extension of semi-L-summands (resp.L-summands). We prove that the following statements are equivalent. (i) Every semi-|·|-summand is a |·|-summand, (ii) (1, 0) is not a vertex of the closed unit ball ofR ² with the norm |·|. In particular semi-L ^p-summands areL ^p-summands whenever 1<p≦∞. The concept of semi-|·|-ideal (resp. |·|-ideal) is introduced in order to extend the one of semi-M-ideal (resp.M-ideal). The following statements are shown to be equivalent. (i) Every semi-|·|-ideal is a |·|-ideal, (ii) every |·|-ideal is a |·|-summand, (iii) (0, 1) is an extreme point of the closed unit ball ofR ² with the norm |·|. From semi-|·|-ideals we define semi-|·|-idealoids in the same way as semi-|·|-ideals arise from semi-|·|-summands. Proper semi-|·|-idealoids are those which are neither semi-|·|-summands nor semi-|·|-ideals. We prove that there is a proper semi-|·|-idealoid if and only if (1, 0) is a vertex and (0, 1) is not an extreme point of the closed unit ball ofR ² with the norm |·|. So there are no proper semi-L ^p-idealoids. The paper concludes by showing thatw*-closed semi-|·|-idealoids in a dual Banach space are semi-|·|-summands, so no new concept appears by predualization of semi-|·|-idealoids.     

A Ramsey theorem for trees

We prove a Ramsey theorem for trees. The infinite version of this theorem can be stated: if T is a rooted tree of infinite height with each node of T having at least one but finitely many immediate successors, if n is a positive integer, and if the collection of all strongly embedded, height-n subtrees of T is partitioned into finitely many classes, then there must exist a strongly embedded subtree S of T with S having infinite height and with all the strongly embedded, height-n subtrees of S in the same class.     

Toughness and Delaunay triangulations

We show that nondegenerate Delaunay triangulations satisfy a combinatorial property called 1-toughness. A graphG is1-tough if for any setP of vertices,c(G–P)|G|, wherec(G–P) is the number of components of the graph obtained by removingP and all attached edges fromG, and |G| is the number of vertices inG. This property arises in the study of Hamiltonian graphs: all Hamiltonian graphs are 1-tough, but not conversely. We also show that all Delaunay triangulationsT satisfy the following closely related property: for any setP of vertices the number of interior components ofT–P is at most |P|–2, where an interior component ofT–P is a component that contains no boundary vertex ofT. These appear to be the first nontrivial properties of a purely combinatorial nature to be established for Delaunay triangulations. We give examples to show that these bounds are best possible and are independent of one another. We also characterize the conditions under which a degenerate Delaunay triangulation can fail to be 1-tough. This characterization leads to a proof that all graphs that can be realized as polytopes inscribed in a sphere are 1-tough. One consequence of the toughness results is that all Delaunay triangulations and all inscribable graphs have perfect matchings.This research was sponsored in part by the National Science Foundation under Grant IRI-88-02457.     

A Note on Aluthge Transforms of Complex Symmetric Operators and Applications

In this paper, we reprove that: (i) the Aluthge transform of a complex symmetric operator [(T)\tilde] = |T|^\frac12 U|T|^\frac12\tilde{T} = |T|^{\frac{1}{2}} U|T|^{\frac{1}{2}} is complex symmetric, (ii) if T is a complex symmetric operator, then ([(T)\tilde])^*(\tilde{T})^{*} and [(T^*)\tilde]\widetilde{T^{*}} are unitarily equivalent. And we also prove that: (iii) if T is a complex symmetric operator, then [((T^*))\tilde]_s,t\widetilde{(T^{*})}_{s,t} and ([(T)\tilde]_t,s)^*(\tilde{T}_{t,s})^{*} are unitarily equivalent for s, t > 0, (iv) if a complex symmetric operator T belongs to class wA(t, t), then T is normal.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

Approximation in the finite element method

Summary The rate of convergence of the finite element method depends on the order to which the solutionu can be approximated by the trial space of piecewise polynomials. We attempt to unify the many published estimates, by proving that if the trial space is complete through polynomials of degreek–1, then it contains a functionv ^h such that |u–v ^h | _s ch ^k–s|u| _k . The derivatives of orders andk are measured either in the maximum norm or in the mean-square norm, and the estimate can be made local: the error in a given element depends on the diameterh _i of that element. The proof applies to domains in any number of dimensions, and employs a uniformity assumption which avoids degenerate element shapes.This research was supported by the National Science Foundation (GP-13778).     

Asymptotics for the wiener sausage with drift

Summary A particle is considered which moves in ^d according to a Brownian motion with drifth0. The space is assumed to contain random traps. The probability of survival of the particle up to timeT decays exponentially asT with a positive decay rate . is shown to be a non-analytic function of |h|. For small |h| the decay rate is given by (h)=1/2|h|²; but if |h| exceeds a certain critical value, (h) depends also on the parameters describing trapping. Upper and lower bounds for (h) are given, which imply the asymptotic linearity of (h) for large |h|. The critical point marks a transition from localized to delocalized behavior. A variational formula for the decay rate is given on the level of generalized processes, which elucidates the mathematical mechanism behind observations made earlier by Grassberger and Procaccia on the basis of computer simulations.Supported by Deutsche Forschungsgemeinschaft     

Minimal extensions of graphs to absolute retracts

A graph H is an absolute retract if for every isometric embedding h of, into a graph G an edge-preserving map g from G to H exists such that g · h is the identity map on H. A vertex v is embeddable in a graph G if G ? v is a retract of G. An absolute retract is uniquely determined by its set of embeddable vertices. We may regard this set as a metric space. We also prove that a graph (finite metric space with integral distance) can be isometrically embedded into only one smallest absolute retract (injective hull). All graphs in this paper are finite, connected, and without multiple edges.     

On weakly τ-quasinormal subgroups of finite groups

Let G be a finite group and H a subgroup of G. We say that: (1) H is τ-quasinormal in G if H permutes with all Sylow subgroups Q of G such that (|Q|, |H|) = 1 and (|H|, |Q ^G |) ≠ 1; (2) H is weakly τ-quasinormal in G if G has a subnormal subgroup T such that HT = G and T ∩ H ≦ H _τG , where H _τG is the subgroup generated by all those subgroups of H which are τ-quasinormal in G. Our main result here is the following. Let ℱ be a saturated formation containing all supersoluble groups and let X ≦ E be normal subgroups of a group G such that G/E ∈ ℱ. Suppose that every non-cyclic Sylow subgroup P of X has a subgroup D such that 1 < |D| < |P| and every subgroup H of P with order |H| = |D| and every cyclic subgroup of P with order 4 (if |D| = 2 and P is non-Abelian) not having a supersoluble supplement in G is weakly τ-quasinormal in G. If X is either E or F* (E), then G ∈ ℱ.