36739594
Generating cycle spaces for graphs on surfaces with small genera
In this paper we investigate cycle base structures of a 2-(edge)-connected graph on surfaces with small genera and show that short cycles do generate the cycle spaces in the case of "small face-embeddings". Examples show that the conditions in our main results are best possible. As applications we find the exact formulae for the minimum lengths of cycle bases of some types of graphs which conclude several known results. Finally, we generalize those results for graphs embedded on general orientable surfaces.
27650319
Generalized Bicycles
Let G = (V,E) be a graph with IZ vertices, and let A4 be a (left) module over a principal ideal domain D. Let Wo(A4) and WI(M) denote the modules of all vertex and edge weightings over M, respectively. An incidence weighting q of G is a weighting of each incident vertex-edge pair (u,e) with an element of D. Now consider an orientation of the edges of G. Let 6, denote the linear operator from We(M) to WI(M) given by 6,(w)(e) = q(u,e)w(u) yl(a,e)w(a), where e E E and u and 1: denote the tail and head of e, respectively. An v-cocycle is a weighting c E WI(M), such that c = 6(w) for some w c We(M). An q-bicycle is an q-cocycle that is also a cycle (ordinary bicycles are obtained when q E 1). Let B,(M) denote the module of all vertex weightings b E We(M), such that 6,(b) is an q-bicycle. For T a spanning tree rooted at vertex c, let q(T) denote the product of q(u,e) over all the edges e of T, where u denotes the end vertex of e that is further from u in T. The q-complexity Z~ of G is the vertex weighting over D, such that 74(c’) is the sum of q(T) over all spanning trees T rooted at t’. In this paper, we show that B,(M) ” M if, and only if 7,,m is nonzero for every nonzero m t M. Further if B,(M) 2 M then B,(M) = { z,,m : m E M}. As special cases of this formula, we obtain results about bicycles, balanced vertex weightings, resistive and leaky electrical networks, handicap ranking of tournaments, and Markov chains. The gcd q-complexity t,, is the greatest common divisor of (7411) : u E V}. We show that t, has a factorization t, = tl t2 t+l, unique up to multiplication by units of D, such that t,+l divides t, and such that for every module M over D, B,(M) is isomorphic to the direct sum of M and the submodules M(t,) = {m E A4 : t,m = 0}, i = 1,. , n 1. The latter formula generalizes the bicycle isomorphism formula given in Berman (1986).
36530209
Determination of the star valency of a graph
The star valency of a graph G is the minimum, over all star decompositions π, of the maximum number of elements in π incident with a vertex. The maximum average degree of G, denoted by dmax-ave(G), is the maximum average degree of all subgraphs of G. In this paper, we prove that the star valency of G is either ⌈dmax-ave(G)/2⌉ or ⌈dmax-ave(G)/2⌉ + 1, and provide a polynomial time algorithm for determining the star valency of a graph.
43519756
The Number of Loopless 4-Regular Maps on the Projective Plane
In this paper rooted loopless (near) 4-regular maps on surfaces such as the sphere and the projective plane are counted and exact formulae with up to three or four parameters for such maps are given. Several classical results on regular maps and one-faced maps are deduced.
39617215
Counting rooted near-triangulations on the sphere
This paper provides the results on the enumerations of rooted simple outerplanar maps, rooted outerplanar near-triangulations, rooted 2-connected near-triangulations, rooted strict 2-connected near-triangulations and rooted simple 2-connected near-triangulations. The answer to an open problem proposed by one of the authors is also provided.
43124802
On the Isomorphisms of Cayley Graphs of Abelian Groups
Let G be a finite group, S a subset of G\{1}, and let Cay (G, S) denote the Cayley digraph of G with respect to S. If, for any subset T of G\{1}, Cay(G, S) ≅ Cay(G, T) implies that Sα = T for some α ∈ Aut(G), then S is called a CI-subset. The group G is called a CIM-group if for any minimal generating subset S of G, S ∪ S-1 is a CI-subset. In this paper, CIM-abelian groups are characterized.
1265218
Solving Regular Tree Grammar Based Constraints
This paper describes the precise specification, design, analysis, implementation, and measurements of an efficient algorithm for solving regular tree grammar based constraints. The particular constraints are for dead-code elimination on recursive data, but the method used for the algorithm design and complexity analysis is general and applies to other program analysis problems as well. The method is centered around Paige's finite differencing, i.e., computing expensive set expressions incrementally, and allows the algorithm to be derived and analyzed formally and implemented easily. We propose higher-level transformations that make the derived algorithm concise and allow its complexity to be analyzed accurately. Although a rough analysis shows that the worst-case time complexity is cubic in program size, an accurate analysis shows that it is linear in the number of live program points and in other parameters, including mainly the arity of data constructors and the number of selector applications into whose arguments the value constructed at a program point might flow. These parameters explain the performance of the analysis in practice. Our implementation also runs two to ten times as fast as a previous implementation of an informally designed algorithm.
5533376
Characterizations of maximum matching graphs of certain types
The maximum matching graph M(G) of a graph G is a graph whose vertices are maximum matchings of G and where two maximum matchings are adjacent in M(G) if they differ in exactly one edge. In this paper, the author characterizes the graphs whose maximum matching graphs are regular or cycles, and adds trees to the list of known maximum matching graphs.
7472011
PCFGs with Syntactic and Prosodic Indicators of Speech Repairs
A grammatical method of combining two kinds of speech repair cues is presented. One cue, prosodic disjuncture, is detected by a decision tree-based ensemble classifier that uses acoustic cues to identify where normal prosody seems to be interrupted (Lickley, 1996). The other cue, syntactic parallelism, codifies the expectation that repairs continue a syntactic category that was left unfinished in the reparandum (Levelt, 1983). The two cues are combined in a Treebank PCFG whose states are split using a few simple tree transformations. Parsing performance on the Switchboard and Fisher corpora suggests that these two cues help to locate speech repairs in a synergistic way.
14694684
A mutual anonymous peer-to-peer protocol design
Peer-to-peer (P2P) computing has become a popular application model because of its easy resource sharing pattern and powerful query search scheme. However, decentralized P2P architecture is scarcely seen to deploy the anonymity on its peers. In this paper, we propose a mutual anonymity protocol, called Secret-sharing-based Mutual Anonymity Protocol (SSMP), for decentralized P2P systems. SSMP employs Shamirs' secret sharing scheme to allow peers to issue queries and responders to deliver requested files anonymously. Compared with previous designs, SSMP achieves mutual anonymity in P2P systems with a high degree of anonymity and a low cryptography processing overhead. We evaluate SSMP by comprehensive simulations.
34451404
The enumeration of near-perfect matchings of factor-critical graphs
Abstract A matching of a graph is a near-perfect matching if it covers all but one vertex. A connected graph G is said to be factor-critical if G − v has perfect matchings for every vertex v of G. In this paper, the enumeration problems for near-perfect matchings in special factor-critical graphs are solved. From this, the exact values of the number of perfect matchings in special bicritical graphs are obtained.