On the Characterization of Maximal Planar Graphs with a Given Signed Cycle Domination Number

Let G =(V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function(SCDF) of G if ∑_(e∈E(C))f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ'_(sc)(G) = min{∑_(e∈E)f(e)| f is an SCDF of G}. This paper will characterize all maximal planar graphs G with order n ≥ 6 and γ'_(sc)(G) = n.     

On induced matchings

Let q^*(G) denote the minimum integer t for which E(G) can be partitioned into t induced matchings of G. Faudree et al. conjectured that q^*(G)d², if G is a bipartite graph and d is the maximum degree of G. In this note, we give an affirmative answer for d=3, the first nontrivial case of this conjecture.     

Consequences of an algorithm for bridged graphs

Chepoi showed that every breadth first search of a bridged graph produces a cop-win ordering of the graph. We note here that Chepoi's proof gives a simple proof of the theorem that G is bridged if and only if G is cop-win and has no induced cycle of length four or five, and that this characterization together with Chepoi's proof reduces the time complexity of bridged graph recognition. Specifically, we show that bridged graph recognition is equivalent to (C₄,C₅)-free graph recognition, and reduce the best known time complexity from O(n⁴) to O(n^3.376).     

A two-sided estimate in the Hsu-Robbins-Erdös law of large numbers

Let X₁, X₂, … be independent identically distributed random variables. Then, Hsu and Robbins (1947) together with Erdös (1949, 1950) have proved that

,

if and only if E[X²₁] < ∞ and E[X₁] = 0. We prove that there are absolute constants C₁, C₂ (0, ∞) such that if X₁, X₂, … are independent identically distributed mean zero random variables, then

c₁λ⁻² E[X₁²·1_{|X1|λ}]S(λ)C₂λ⁻² E[X₁²·1_{|X1|λ}]

,

for every λ > 0.     

Circular permutation graph family with applications

In a circular permutation diagram, there are two sets of terminals on two concentric circles: C_in and C_out. Given a permutation Π = [π₁, π₂, …, π_n], terminal i on C_in and terminal π_i on C_out are connected by a wire. The intersection graph G_c of a circular permutation diagram D_c is called a circular permutation graph of a permutation Π corresponding to the diagram D_c. The set of all circular permutation graphs of a permutation Π is called the circular permutation graph family of permutation Π. In this paper, we propose the following: (1) an O(V + E) time algorithm to check if a labeled graph G = (V, E) is a labeled circular permutation graph. (2) An O(n log n + nt) time algorithm to find a maximum independent set of a family, where n = Π and t is the cardinality of the output. (Number t in the worst case is O(n). However, if Π is uniformly distributed (and independent from i), its expected value is O(√n).) (3) An O(min(δV_clog logV_c,V_clogV_c) + E_c) time algorithm for finding a maximum independent set of a circular permutation diagram D_c, where δ is the minimum degree of vertices in the intersection graph G_c = (V_c,E_c) of D_c. (4) An O(n log log n) time algorithm for finding a maximum clique and the chromatic number of a circular permutation diagram, where n is the number of wires in the diagram.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

Regular automorphisms of order p2

Let G be a group, and let α be a regular automorphism of order p² of G, where p is a prime. If G is polycyclic-by-finite and the map ϕ : G →G defined by g^ϕ= [g,α] is surjective, then G is soluble. If G is polycyclic, then C_G(α^p) and G/[G,α^p] are both nilpotent-by-finite.     

Biased partitions and judicious <Emphasis Type="Italic">k</Emphasis>-partitions of graphs

Let G = (V,E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1- p, let m_p(G) be the minimum of qe(V₁) +pe(V₂) over partitions V = V₁ ∪ V₂, where e(V_i) denotes the number of edges spanned by V_i. We show that if mp(G) = pqm-δ, then there exists a bipartition V₁, V₂ of G such that e(V₁) ≤ p²m - δ + p√m/2 + o(√m) and e(V₂) ≤ q²m - δ + q √m/2 + o(√m) for δ = o(m^2/3). This is sharp for complete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) = (1 - 1/k)m + α, then G admits a k-partition such that each vertex class spans at most m/k² - Ω(m/k^7.5) edges for α = Ω(m/k⁶). Both of the above improve the results of Bollobás and Scott.     

On total covers of graphs

A total cover of a graph G is a subset of V(G)E(G) which covers all elements of V(G)E(G). The total covering number ₂(G) of a graph G is the minimum cardinality of a total cover in G. In [1], it is proven that ₂(G)[n/2] for a connected graph G of order n. Here we consider the extremal case and give some properties of connected graphs which have a total covering number [n/2]. We prove that such a graph with even order has a 1-factor and such a graph with odd order is factor-critical.     

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次.图G的(s,t)-松弛强边着色指数,记作x'(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值.在图G中...     

Bounded rank of C-algebras

We introduce a concept of the bounded rank (with respect to a positive constant) for unital C^*-algebras as a modification of the usual real rank and present a series of conditions insuring that bounded and real ranks coincide. These observations are then used to prove that for a given n and K>0 there exists a separable unital C^*-algebra Z_n^K such that every other separable unital C^*-algebra of bounded rank with respect to K at most n is a quotient of Z_n^K.     

Enumeration of irreducible binary words

Overlap free words over two letters are called irreducible binary words. Let d(n) denote the number of irreducible binary words of length n. In this paper we show that there are positive constants C₁ and C₂ such that C₁n^1.155<d(n)<C₂n^1.587 holds for all n>0.     

Embeddings of the base and bundle isomorphisms

Let π_i :E_i→M, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections s_i :M→E_i. Suppose that U is an open neighborhood of s₁(M) in E₁ and F :U→E₂ a smooth embedding so that π₂Fs₁ :M→M is homotopic to a diffeomorphism f. We show that if k>[(n+1)/2]+1 then E₁ and the induced bundle f^*E₂ are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [(n+1)/2]+1<kn we give examples of nonisomorphic oriented bundles E₁ and E₂ of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E₁ and f^*E₂ are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[(n+1)/2]+1 and M is a homotopy n-sphere.     

Complete-factors and f-factors

A factor F of a graph is called a complete-factor if each component of F is complete. Let G be a graph, F be a complete-factor of G with ω(F)2, and f be an integer-valued function defined on V(G) with ∑_xV(G)f(x) even. If G−V(C) has an f-factor for each component C of F, then G has an f-factor.     

Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

The chromatic difference sequence of the Cartesian product of graphs

The chromatic difference sequence cds(G) of a graph G with chromatic number n is defined by cds(G) = (a(1), a(2),…, a(n)) if the sum of a(1), a(2),…, a(t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□H, has the vertex set V(G□H = V(G) x V(H) and its edge set is given by (x₁, y₁)(x₂, y₂) ε E(G□H) if either x₁ = x₂ and y₁ y₂ ε E(H) or y₁ = y₂ and x₁x₂ ε E(G).

We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.     

Property T and strong property T for unital*-homomorphisms

We introduce and study property T and strong property T for unital*-homomorphisms between two unital C^*-algebras.We also consider the relations between property T and invariant subspaces for some canonical unital^-representations.As a corollary,we show that when G is a discrete group,G is finite if and only if G is amenable and the inclusion map i:Cr^*(G)→B(l^2(G))has property T.We also give some new equivalent forms of property T for countable discrete groups and strong property T for unital C^*-algebras.