Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².     

Numerical ranges of cube roots of the identity

The numerical range of a bounded linear operator T on a Hilbert space H is defined to be the subset W(T)={〈Tv,v〉:v∈H,∥v∥=1} of the complex plane. For operators on a finite-dimensional Hilbert space, it is known that if W(T) is a circular disk then the center of the disk must be a multiple eigenvalue of T. In particular, if T has minimal polynomial z³-1, then W(T) cannot be a circular disk. In this paper we show that this is no longer the case when H is infinite dimensional. The collection of 3×3 matrices with three-fold symmetry about the origin are also classified.     

Some generalizations of the concept of a p-space

In this article, some generalizations of the concept of a p-space are introduced and studied. The notion of a source of a space in a larger space and the concepts of partial plumage, s-embedding, p-embedding, p^?-embedding, s-space, and p^?-space are defined and studied in depth (see Theorems 2.6, 2.7, 3.2, 4.3, 4.4, 4.10 and their corollaries). An example of a hereditarily p^?-space which is not a p-space and is a perfect image of a hereditarily p-space is indicated (Example 2.9). Among the main results, we establish that if a paracompact space X is p-embedded in a pseudocompact space as a dense subspace, then X is a p-space (Corollary 4.8), and that if X has a countable network and is p^?-embedded in a pseudocompact space, then X is metrizable (Corollary 4.11). The following problem is posed: is every paracompact Gδ-subspace of a pseudocompact space ?ech-complete?     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

Fall colouring of bipartite graphs and cartesian products of graphs

The question of whether a graph can be partitioned into k independent dominating sets, which is the same as having a fallk-colouring, is considered. For k=3, it is shown that a graph G can be partitioned into three independent dominating sets if and only if the cartesian product G□K₂ can be partitioned into three independent dominating sets. The graph K₂ can be replaced by any graph H such that there is a mapping f:Q_n→H, where f is a type-II graph homomorphism.The cartesian product of two trees is considered, as well as the complexity of partitioning a bipartite graph into three independent dominating sets, which is shown to be NP-complete. For other values of k, iterated cartesian products are considered, leading to a result that shows for what values of k the hypercubes can be partitioned into k independent dominating sets.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

Characterizations of isomorphisms and derivations of some algebras

Let ? be a zero-product preserving bijective bounded linear map from a unital algebra A onto a unital algebra B such that ?(1)=k. We show that if A is a CSL algebra on a Hilbert space or a J-lattice algebra on a Banach space then there exists an isomorphism ψ from A onto B such that ?=kψ. For a nest algebra A in a factor von Neumann algebra, we characterize the linear maps on A such that δ(x)y+xδ(y)=0 for all x,y∈A with xy=0.     

On the generation of bicliques of a graph

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X∪Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y≠∅, then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.     

On the determination of the basin of attraction of a periodic orbit in two-dimensional systems

We consider the general nonlinear differential equation with x∈R² and develop a method to determine the basin of attraction of a periodic orbit. Borg's criterion provides a method to prove existence, uniqueness and exponential stability of a periodic orbit and to determine a subset of its basin of attraction. In order to use the criterion one has to find a function W∈C¹(R²,R) such that LW(x)=W^′(x)+L(x) is negative for all x∈K, where K is a positively invariant set. Here, L(x) is a given function and W^′(x) denotes the orbital derivative of W. In this paper we prove the existence and smoothness of a function W such that LW(x)=−μ‖f(x)‖. We approximate the function W, which satisfies the linear partial differential equation W^′(x)=〈∇W(x),f(x)〉=−μ‖f(x)‖−L(x), using radial basis functions and obtain an approximation w such that Lw(x)<0. Using radial basis functions again, we determine a positively invariant set K so that we can apply Borg's criterion. As an example we apply the method to the Van-der-Pol equation.     

On the equality of the partial Grundy and upper ochromatic numbers of graphs

A (proper) k-coloring of a graph G is a partition Π={V₁,V₂,…,V_k} of V(G) into k independent sets, called color classes. In a k-coloring Π, a vertex v∈V_i is called a Grundy vertex if v is adjacent to at least one vertex in color class V_j, for every j, j<i. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. In this paper we introduce partial Grundy colorings, and relate them to parsimonious proper colorings introduced by Simmons in 1982.     

Extensions of zip rings

A ring R is called right zip provided that if the right annihilator r_R(X) of a subset X of R is zero, r_R(Y)=0 for a finite subset Y⊆X. Faith [5] raised the following questions: When does R being a right zip ring imply R[x] being right zip?; Characterize a ring R such that Mat_n(R) is right zip; When does R being a right zip ring imply R[G] being right zip when G is a finite group? In this note, we continue the study of the extensions of noncommutative zip rings based on Faith's questions.     

Normality of products of monotonically normal spaces with compact spaces

Let S be the class of all spaces, each of which is homeomorphic to a stationary subset of a regular uncountable cardinal (depending on the space). In this paper, we prove the following result: The product X×C of a monotonically normal space X and a compact space C is normal if and only if S×C is normal for each closed subspace S in X belonging to S. As a corollary, we obtain the following result: If the product of a monotonically normal space and a compact space is orthocompact, then it is normal.     

A characterization of block graphs

A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let N_e(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈N_e(u) and y∈N_e(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22].     

A study 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 the arcs of G as vertices such that two arcs uv,xy are adjacent if and only if (v,u,x,y) is a 3-arc of G. In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs.     

Automatic continuity and representation of group homomorphisms defined between groups of continuous functions

Let C(X,G) be the group of continuous functions from a topological space X into a topological group G with pointwise multiplication as the composition law, endowed with the uniform convergence topology. To what extent does the group structure of C(X,G) determine the topology of X? More generally, when does the existence of a group homomorphism H between the groups C(X,G) and C(Y,G) implies that there is a continuous map h of Y into X such that H is canonically represented by h? We prove that, for any topological group G and compact spaces X and Y, every non-vanishing C-isomorphism (defined below) H of C(X,G) into C(Y,G) is automatically continuous and can be canonically represented by a continuous map h of Y into X. Some applications to specific groups and examples are given in the paper.     

On the characteristic polynomial of a special class of graphs and spectra of balanced trees

Let H be a simple graph with n vertices and G be a sequence of n rooted graphs G₁,G₂,…,G_n. Godsil and McKay [C.D. Godsil, B.D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978) 21-28] defined the rooted product H(G), of H by G by identifying the root vertex of G_i with the ith vertex of H, and determined the characteristic polynomial of H(G). In this paper we prove a general result on the determinants of some special matrices and, as a corollary, determine the characteristic polynomials of adjacency and Laplacian matrices of H(G).Rojo and Soto [O. Rojo, R. Soto, The spectra of the adjacency matrix and Laplacian matrix for some balanced trees, Linear Algebra Appl. 403 (2005) 97-117] computed the characteristic polynomials and the spectrum of adjacency and Laplacian matrices of a class of balanced trees. As an application of our results, we obtain their conclusions by a simple method.     

Groups of quasi-invariance and the Pontryagin duality

A Polish group G is called a group of quasi-invariance or a QI-group, if there exist a locally compact group X and a probability measure μ on X such that (1) there exists a continuous monomorphism ? from G into X with dense image, and (2) for each g∈X either g∈?(G) and the shift μg is equivalent to μ or g∉?(G) and μg is orthogonal to μ. It is proved that ?(G) is a σ-compact subset of X. We show that there exists a Polish non-locally quasi-convex (and hence nonreflexive) QI-group such that its bidual is not a QI-group. It is proved also that the bidual group of a QI-group may be not a saturated subgroup of X. It is constructed a reflexive non-discrete group topology on the integers.     

Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.     

Degree-bounded factorizations of bipartite multigraphs and of pseudographs

For d≥1, s≥0 a (d,d+s)-graph is a graph whose degrees all lie in the interval {d,d+1,…,d+s}. For r≥1, a≥0 an (r,r+a)-factor of a graph G is a spanning (r,r+a)-subgraph of G. An (r,r+a)-factorization of a graph G is a decomposition of G into edge-disjoint (r,r+a)-factors. A graph is (r,r+a)-factorable if it has an (r,r+a)-factorization.We prove a number of results about (r,r+a)-factorizations of (d,d+s)-bipartite multigraphs and of (d,d+s)-pseudographs (multigraphs with loops permitted). For example, for t≥1 let β(r,s,a,t) be the least integer such that, if d≥β(r,s,a,t) then every (d,d+s)-bipartite multigraph G is (r,r+a)-factorable with x(r,r+a)-factors for at least t different values of x. Then we show that