Eccentric graphs

For any graph G we define the eccentric graph G_e on the same set of vertices, by joining two vertices in G_e if and only if one of the vertices has maximum possible distance from the other. The following results are given in this paper:

• (1)A few general properties of eccentric graphs.
• (2)A characterization of graphs G with G_e = K_p and with G_e = pK₂.
• (3)A solution of the equation G_e = G¯.

     

Boolean approach to planar embeddings of a graph

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.

1. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
2. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2 ^c(H)?1, wherec (H) is the number of the components of the graphH which is related toG.

     

Symplectic geometry,minors and graph Laplacians

In my talk, I will present some works done in the nineties on Laplacians on graphs: from eigenvalue problems to inverse problem for resistor networks. I will focus on the motivations and the main results as well as on the main ideas:

• •A differential topology point of view on the minor relation: a nice stratification associated to a finite graph Γ whose strata are associated to the minors of Γ
• •“Discrete” (graphs) versus “continuous” (Riemannian manifolds)
• •Stability of spectra with respect to singular limits: a finite dimensional theory of operators with domains (Von Neumann theory).

The link with topology will appear in some results about my graph parameter μ, in particular the planarity and the linkless embedding properties.     

On the geometry of the characteristic vector of an lcQS-manifold

We study conditions under which the characteristic vector of a normal lcQS-manifold is a torsion-forming or even a concircular vector field. We prove that the following assertions are equivalent:

• An lcQS-structure is normal, and its characteristic vector is a torsion-forming vector field.
• An lcQS-structure is normal, and its characteristic vector is a concircular vector field.
• An lcQS-structure is locally conformally cosymplectic and has a closed contact form.

     

Curvature Dimension Inequalities and Subelliptic Heat Kernel Gradient Bounds on Contact Manifolds

We study curvature dimension inequalities for the sub-Laplacian on contact Riemannian manifolds. This new curvature dimension condition is then used to obtain:

• Geometric conditions ensuring the compactness of the underlying manifold (Bonnet–Myers type results);
• Volume estimates of metric balls;
• Gradient bounds and stochastic completeness for the heat semigroup generated by the sub-Laplacian;
• Spectral gap estimates.

     

Dynamic graph models

Research in graph theory has focused on studying the structure of graphs with the assumption that they are static. However, in many applications, the graphs that arise change with time, i.e., they are dynamic in nature. This is especially true of applications involving graph models in computer science. We present an expository study of dynamic graphs with the main driving force being practical applications. We first develop a formal classification of dynamic graphs. This taxonomy in the form of generalizations and extensions will in turn suggest new areas of application. Next, we discuss areas where dynamic graphs arise in computer science such as compilers, databases, fault-tolerance, artificial intelligence, and computer networks. Finally, we propose approaches that can be used for studying dynamic graphs. The main objective in any study of dynamic graphs should be to

• 1.(i) extend results developed for static graph theory to dynamic graphs,
• 2.(ii) study the properties that describe how a dynamic graph changes,
• 3.(iii) investigate problems and issues in dynamic graph theory that are raised by practical applications of dynamic graphs in computer science.

     

Graph bisection algorithms with good average case behavior

In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n ^{1?1/[(d+1)/2]}), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n ^2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:

1. the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,
2. whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),
3. the algorithm works well both theoretically and experimentally,
4. the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and
5. the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).

     

Constructing a perfect matching is in random NC

We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. We also show that several related problems lie in Random NC. These include:

1. Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation;
2. Constructing a maximum-cardinality matching;
3. Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary;
4. Constructing a maximums-t flow in a directed graph whose edge weights are given in unary.

     

Monotonicity and error bounds for networks of Erlang loss queues

Networks of Erlang loss queues naturally arise when modelling finite communication systems without delays, among which, most notably are

1. classical circuit switch telephone networks (loss networks) and
2. present-day wireless mobile networks.

Performance measures of interest such as loss probabilities or throughputs can be obtained from the steady state distribution. However, while this steady state distribution has a closed product form expression in the first case (loss networks), it does not have one in the second case due to blocked (and lost) handovers. Product form approximations are therefore suggested. These approximations are obtained by a combined modification of both the state space (by a hypercubic expansion) and the transition rates (by extra redial rates). It will be shown that these product form approximations lead to

• upper bounds for loss probabilities and
• analytic error bounds for the accuracy of the approximation for various performance measures.

The proofs of these results rely upon both monotonicity results and an analytic error bound method as based on Markov reward theory. This combination and its technicalities are of interest by themselves. The technical conditions are worked out and verified for two specific applications:

• pure loss networks as under (i)
• GSM networks with fixed channel allocation as under (ii).

The results are of practical interest for computational simplifications and, particularly, to guarantee that blocking probabilities do not exceed a given threshold such as for network dimensioning.     

Stability and boundedness of a kind of third-order delay differential system

The paper studies equation (1.1) in two cases:

• •(i)p ≡ 0,
• •(ii)p ≠ 0.

In Case (i), the asymptotic stability of the solution x = 0 is studied; in Case (ii), the uniform boundedness and uniform ultimate boundedness of all solutions of (1.1) are proved.     

Symmetric differentials, Kähler groups and ball quotients

While Margulis’ superrigidity theorem completely describes the finite dimensional linear representations of lattices of higher rank simple real Lie groups, almost nothing is known concerning the representation theory of complex hyperbolic lattices. The main result of this paper (Theorem 1.3) is a strong rigidity theorem for a certain class of cocompact arithmetic complex hyperbolic lattices. It relies on the following two ingredients:

• Theorem 1.6 showing that the representations of the topological fundamental group of a compact Kähler manifold X are controlled by the global symmetric differentials on X.
• An arithmetic vanishing theorem for global symmetric differentials on certain compact ball quotients using automorphic forms, in particular deep results of Clozel on base change (Theorem 1.11).

     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

Slightly triangulated graphs are perfect

A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C _k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;

1. G contains no chordless cycle with at least 5 vertices.
2. For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.

     

On degree sequences of undirected,directed, and bidirected graphs

Bidirected graphs generalize directed and undirected graphs in that edges are oriented locally at every node. The natural notion of the degree of a node that takes into account (local) orientations is that of net-degree. In this paper, we extend the following four topics from (un)directed graphs to bidirected graphs:

• –Erdős–Gallai-type results: characterization of net-degree sequences,
• –Havel–Hakimi-type results: complete sets of degree-preserving operations,
• –Extremal degree sequences: characterization of uniquely realizable sequences, and
• –Enumerative aspects: counting formulas for net-degree sequences.

To underline the similarities and differences to their (un)directed counterparts, we briefly survey the undirected setting and we give a thorough account for digraphs with an emphasis on the discrete geometry of degree sequences. In particular, we determine the tight and uniquely realizable degree sequences for directed graphs.     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

On the computational complexity of the theory of Abelian groups

We develop a series of Ehrenfeucht games and prove the following results:

• 1.(i) The first order theory of the divisible and indecomposable p-group, the first order theory of the group of rational numbers with denominators prime to p and the first order theory of a cyclic group of prime power order can be decided in 2^{2cn log n} Turing time.
• 2.(ii) The first order theory of the direct sum of countably many infinite cyclic groups, the first order theory of finite Abelian groups and the first order theory of all Abelian groups can be decided in 2^2dn Turing space.

     

Note on vertex degrees of planar graphs

In this note the second moment of the vertex degree sequence of planar graphs is considered. We prove that

• 1 If G is an outerplanar graph of order n ? 3 then

• 2 If G is a planar graph of order n ? 4 then

where d₁,…,d_n is the vertex degree sequence of G. We exhibit all graphs for which these upper bounds are attained.     

An optimal time to sleep for an auto-sleep system considering multi-usage states

An auto-sleep system is defined by the following two properties:

• 1.(i) a call for the system occurs randomly and intermittently
• 2.(ii) the system automatically goes to sleep if there occurs no call during a prespecified time T.

It considers four states:

• 1.(a) sleep
• 2.(b) warm-up
• 3.(c) nonusage
• 4.(d) usage.

For such a system, the time to sleep has been discussed based on suitable criteria. This study extends the model for an auto-sleep system so that the model can deal with multi-usage states. With a view to determining an optimal time to sleep under the extended model, the expected energy consumed per unit time is formulated as a criterion to be minimized. The existence of an optimal time to sleep is examined under a general call distribution. Numerical examples are also provided for a Weibull as well as a log-normal call distribution.     

Cyclic algebras,complete fields,and crossed products

Theorem 1

Let q=char(k). Let M be a subfield of D which is Galois over K of degree m with Galois group H.

1. If q/m then H has a normal q-Sylow subgroup.
2. Iq q ? m then H is an abelian group with one or two generators, an extension of a cyclic group by a cyclic group of order e where k contains a primitive e-th root of unity.

Letk(X) be the generic division ring overk of indexn as defined by Amitsur.

Theorem 2

If n is divisible by the square of a prime p≠char(k) and k does not contain a primitive p-th root of unity, then k(X) is not a crossed product.     

Invariant connections and invariant holomorphic bundles on homogeneous manifolds

Let X be a differentiable manifold endowed with a transitive action α: A×X→X of a Lie group A. Let K be a Lie group. Under suitable technical assumptions, we give explicit classification theorems, in terms of explicit finite dimensional quotients, of three classes of objects:

• equivalence classes of α-invariant K-connections on X
• α-invariant gauge classes of K-connections on X, and
• α-invariant isomorphism classes of pairs (Q,P) consisting of a holomorphic K ^?-bundle Q → X and a K-reduction P of Q (when X has an α-invariant complex structure).