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.
12158249
Bisingular maps on the sphere and the projective plane
Abstract A map is bisingular if each edge is either a loop or an isthmus (i.e., on the boundary of the same face). In this paper we study the number of rooted bisingular maps on the plane or projective plane and also we present formulae for such maps with up to three or more parameters: the root valency, the number of isthmus, the number of essential loops, and the number of planar loops.
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.
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.
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.
4409694
On route selection for interdomain traffic engineering
In this article we investigate a model of route selection for interdomain traffic engineering where routing to multiple destinations can be coordinated. We identify potential routing instability and inefficiency problems, and derive a set of practical guidelines to guarantee stability without global coordination. Using a realistic Internet topology, we show that route oscillations can happen even when a small number of ASes coordinate route selection for just a small number of destinations if the coordination does not follow our guidelines. Wc further extend our model so that ASes can adopt any route selection algorithms in a class of algorithms we call rational route selection algorithms; and the local ranking of routes of an AS can depend on ingress traffic patterns. We show that persistent route oscillations can happen in certain network settings even if the ASes strictly follow the constraints imposed by business considerations, and adopt any rational route selection algorithms.
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.
2269541
Principal component analysis for predicting transcription-factor binding motifs from array-derived data
BackgroundThe responses to interleukin 1 (IL-1) in human chondrocytes constitute a complex regulatory mechanism, where multiple transcription factors interact combinatorially to transcription-factor binding motifs (TFBMs). In order to select a critical set of TFBMs from genomic DNA information and an array-derived data, an efficient algorithm to solve a combinatorial optimization problem is required. Although computational approaches based on evolutionary algorithms are commonly employed, an analytical algorithm would be useful to predict TFBMs at nearly no computational cost and evaluate varying modelling conditions. Singular value decomposition (SVD) is a powerful method to derive primary components of a given matrix. Applying SVD to a promoter matrix defined from regulatory DNA sequences, we derived a novel method to predict the critical set of TFBMs.ResultsThe promoter matrix was defined to establish a quantitative relationship between the IL-1-driven mRNA alteration and genomic DNA sequences of the IL-1 responsive genes. The matrix was decomposed with SVD, and the effects of 8 potential TFBMs (5'-CAGGC-3', 5'-CGCCC-3', 5'-CCGCC-3', 5'-ATGGG-3', 5'-GGGAA-3', 5'-CGTCC-3', 5'-AAAGG-3', and 5'-ACCCA-3') were predicted from a pool of 512 random DNA sequences. The prediction included matches to the core binding motifs of biologically known TFBMs such as AP2, SP1, EGR1, KROX, GC-BOX, ABI4, ETF, E2F, SRF, STAT, IK-1, PPARγ, STAF, ROAZ, and NFκB, and their significance was evaluated numerically using Monte Carlo simulation and genetic algorithm.ConclusionThe described SVD-based prediction is an analytical method to provide a set of potential TFBMs involved in transcriptional regulation. The results would be useful to evaluate analytically a contribution of individual DNA sequences.
13098192
On the impact of concurrent downloads
Concurrent downloads accelerate information access speed for individual Web users. The speed-up comes from multiple connections launched for one subject download, which leads to unfairness at user level. We study the impact of concurrent downloads on the network. Particularly, we investigate the fairness between users who employ different downloading concurrency. We also discuss how concurrent downloads affect the transient behavior of the network.
43698695
The fractional matching numbers of graphs
A fractional matching of a graph G is a function f that assigns to each edge a number in [0, 1] such that, for each vertex v, ∑ f(e) ≤ 1, where the sum is taken over all edges incident to v. The fractional matching number of G is the supremum of ∑e∈E(G)f(e) over all fractional matchings f. In this paper, we provide a new formula for calculating the fractional matching numbers of graphs using the Gallai–Edmonds Structure Theorem. Thus, we characterize graphs for which the fractional matching number equals the matching number and graphs for which the fractional matching number is the maximum possible (one-half the number of vertices). © 2002 Wiley Periodicals, Inc.