𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Convexity Lemma and Expansion Procedures for Bipartite Graphs

✍ Scribed by W. Imrich; S. Klavžar

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
148 KB
Volume
19
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

A hierarchy of classes of graphs is proposed which includes hypercubes, acyclic cubical complexes, median graphs, almost-median graphs, semi-median graphs and partial cubes. Structural properties of these classes are derived and used for the characterization of these classes by expansion procedures, for a characterization of semi-median graphs by metrically defined relations on the edge set of a graph and for a characterization of median graphs by forbidden subgraphs. Moreover, a convexity lemma is proved and used to derive a simple algorithm of complexity O(mn) for recognizing median graphs.

📜 SIMILAR VOLUMES

A sufficient condition for bipartite gra
A sufficient condition for bipartite graphs to be type one
✍ Xu, Baogang 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 2 views

The total chromatic number χ T (G) of graph G is the least number of colors assigned to V (G) ∪ E(G) such that no adjacent or incident elements receive the same color. In this article, we give a sufficient condition for a bipartite graph G to have χ T (G) = ∆(G) + 1.

A convex optimization procedure to compu
A convex optimization procedure to compute ℋ2 and ℋ∞ norms for uncertain linear systems in polytopic domains
✍ Ricardo C. L. F. Oliveira; Pedro L. D. Peres 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB

## Abstract In this paper, a convergent numerical procedure to compute ℋ︁~2~ and ℋ︁~∞~ norms of uncertain time‐invariant linear systems in polytopic domains is proposed. The norms are characterized by means of homogeneous polynomially parameter‐dependent Lyapunov functions of arbitrary degree __g__