Proceedings of the First Japan Conference on Graph Theory by J. Akiyama, Y. Egawa and H. Enomoto (Eds.)

By J. Akiyama, Y. Egawa and H. Enomoto (Eds.)

Show description

Read or Download Proceedings of the First Japan Conference on Graph Theory and Applications, Hakone, Japan, June 1-5, 1986 PDF

Best graph theory books

Managing and Mining Graph Data

Managing and Mining Graph info is a accomplished survey e-book in graph administration and mining. It includes broad surveys on numerous very important graph subject matters akin to graph languages, indexing, clustering, facts iteration, trend mining, class, key-phrase seek, development matching, and privateness. It additionally experiences a few domain-specific eventualities resembling move mining, internet graphs, social networks, chemical and organic information. The chapters are written through popular researchers within the box, and supply a vast point of view of the world. this can be the 1st complete survey booklet within the rising subject of graph info processing.

Managing and Mining Graph information is designed for a diversified viewers composed of professors, researchers and practitioners in undefined. This quantity can also be appropriate as a reference publication for advanced-level database scholars in laptop technological know-how and engineering.

Tree lattices

Crew activities on bushes provide a unified geometric approach of recasting the bankruptcy of combinatorial crew concept facing unfastened teams, amalgams, and HNN extensions. many of the relevant examples come up from rank one uncomplicated Lie teams over a non-archimedean neighborhood box performing on their Bruhat--Tits timber.

Genetic Theory for Cubic Graphs

This ebook was once encouraged by means of the thought that many of the underlying hassle in not easy situations of graph-based difficulties (e. g. , the touring Salesman challenge) should be “inherited” from less complicated graphs which – in a suitable feel – can be obvious as “ancestors” of the given graph example. The authors suggest a partitioning of the set of unlabeled, hooked up cubic graphs into disjoint subsets named genes and descendants, the place the cardinality of the descendants dominates that of the genes.

Extra info for Proceedings of the First Japan Conference on Graph Theory and Applications, Hakone, Japan, June 1-5, 1986

Sample text

An operational state of G corresponds to a state of each cutset in which each has at least one operational edge, although the converse need not hold. Hence the probability that each cutset has at least one operational edge is an upper bound on the reliability of G. This can be easily evaluated, as the cutsets are edge-disjoint. The bound is improved by taking more cutsets, and cutsets which are more likely to fail; again, these two goals may be conflicting. We consider the simplest case of requiring an edge-packing by a maximum number of cutsets.

This can be seen from the graphs Gl and G2in Fig. 1. It is easy to see, in fact, that for any graph G, Y ' ( W = B d G ) 6 B-(G) B + W = Bl(G) where y'(G) is the edge domination number of G. 2),(3,419 ( 5 3 6 ) ) . Next, we let S = V ( G )and let X E S have property P if and only if X contains no closed neighborhood of G. e. a minimal dominating set of G. The cardinalities of a largest and a smallest minimal dominating set are denoted T ( G ) and y(G), respectively. Let flf(G) and fl;(C) denote the cardinality of largest and smallest P-sets, respectively.

T. HEDETNIEMI* Department of Computer Science, Clemson University R. LASKAR* Department of Mathematical Sciences, Clemson University Received 30 September 1986 Revised 18 March 1987 1. Introduction In 1959 Gallai [4] presented his now classical theorem, involving the vertex covering number ao, the vertex independence number Po, the edge covering number a l , and the maximum matching (or edge independence) number B1. Theorem 1 (Gallai). For any nontrivial, connected graph G = ( V , E ) with p vertices, I.

Download PDF sample

Rated 4.92 of 5 – based on 47 votes