✦ LIBER ✦

Boolean distance for graphs

✍ Scribed by Frank Harary; Robert A. Melter; Uri N. Peled; Ioan Tomescu

Book ID: 103057651
Publisher: Elsevier Science
Year: 1982
Tongue: English
Weight: 576 KB
Volume: 39
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(82)90135-2

No coin nor oath required. For personal study only.

✦ Synopsis

The boolear? distance between twc points x and y of a connected graph G is defined as the set of all points on all paths joining x and y in G (@ if x = y). It is determined in terms of the block-cutpoint graph of G, and shown to satisfy the triangle inequality b(x, y)c_ b(x, z)U b(z, y). We denote by B(G) the collection of distinct boolean distances of G and by M(G) the multiset of the distances together lINith the number of occurrences of each of them. Then (B(G)/ = 1 +(bl') where b is the number of blocks of G. A combinatorial characterization is given for B(T) where T is a tree. Finally, G is reconstructible from M(G) if and only if every block of G is a line or a triangle.

📜 SIMILAR VOLUMES

Boolean-width of graphs

✍ Binh-Minh Bui-Xuan; Jan Arne Telle; Martin Vatshelle 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 449 KB

Cryptographic Boolean Functions and Appl

Cryptographic Boolean Functions and Applications || Boolean Cayley graphs

✍ Cusick, Thomas W. 📂 Article 📅 2009 🏛 Elsevier 🌐 English ⚖ 767 KB

Boolean functions are the building blocks of symmetric cryptographic systems. Symmetrical cryptographic algorithms are fundamental tools in the design of all types of digital security systems (i.e. communications, financial and e-commerce). Cryptographic Boolean Functions and Applications is a

Boolean planarity characterization of gr

Boolean planarity characterization of graphs

✍ Liu Yanpei 📂 Article 📅 1988 🏛 Institute of Mathematics, Chinese Academy of Scien 🌐 English ⚖ 669 KB

Distances and volumina for graphs

✍ D.J. Klein; H.‐Y. Zhu 📂 Article 📅 1998 🏛 Springer 🌐 English ⚖ 210 KB

Distance-Balanced Graphs

✍ Janja Jerebic; Sandi Klavžar; Douglas F. Rall 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 195 KB

Orientation distance graphs

✍ Gary Chartrand; David Erwin; Michael Raines; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

For two nonisomorphic orientations D and D H of a graph G, the orientation distance d o (D,D H ) between D and D H is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D H . The orientation distance graph h o (G) of G has the set y(G) of pairwi