✦ LIBER ✦

Characterizations of two classes of digraphs

✍ Scribed by Zygmunt Jackowski

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 796 KB
Volume: 133
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90022-1

No coin nor oath required. For personal study only.

✦ Synopsis

In the paper we present two characterizations of classes of digraphs. The first is a forbidden triple characterization of digraphs with augmented adjacency matrices having consecutive ones property for columns. The second is a forbidden circuit characterization of digraphs with totally balanced augmented adjacency matrices. The characterizations yield polynomial time algorithms for finding the forbidden structures. Moreover, we prove that in each forbidden circuit we can easily find a forbidden triple of vertices.

📜 SIMILAR VOLUMES

New characterizations of digraphs repres

New characterizations of digraphs represented by intervals

✍ Sanyal, Barun K.; Sen, Malay K. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

We present new characterizations of interval digraphs, interval graphs, and indifference digraphs, using linear orderings of edges and vertices.

Characterizations of Schunck Classes of

Characterizations of Schunck Classes of Finite Soluble Groups

✍ A. Ballester-Bolinches; M.C. Pedraza-Aguilera; M.D. Pérez-Ramos 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 128 KB

All groups considered in this paper are finite and soluble. Characterization of Schunck classes and saturated formations by means of certain embedding properties of their associated projectors plays an important part in the Theory of Classes of Groups. Schunck classes whose projectors are normal su

A class of vertex-transitive digraphs

✍ Chong-Yun Chao; Jacqueline G Wells 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 571 KB

Characterizations of vertex pancyclic an

Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs

✍ G. Gutin 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 527 KB

A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a complete multipartite graph. Such a digraph D is called ordinary if for any pair X, Y of its partite sets the set of arcs with both end vert

Factors in a class of regular digraphs

✍ M. V. S. Ramanath 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 634 KB

For the class of 2-diregular digraphs: (1) We give a simple closed form expression-a power of 2-for the number of difactors. (2) For the adjacency matrices of these graphs, we show an intimate relationship between the permanent and determinant. (3) We give a necessary and sufficient condition for th

Characterizations of Learnability for Cl

Characterizations of Learnability for Classes of {0, ..., n)-Valued Functions

✍ S. Bendavid; N. Cesabianchi; D. Haussler; P.M. Long 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 885 KB

We investigate the PAC learnability of classes of \(\{0, \ldots, n\}\)-valued functions \((n<\infty)\). For \(n=1\) it is known that the finiteness of the Vapnik-Chervonenkis dimension is necessary and sulficient for learning. For \(n>1\) several generalizations of the VC-dimension, each yielding a