A
straight-ahead walk in an embedded Eulerian graph
G always passes from an edge to the opposite edge in the rotation at the same vertex. A straight-ahead walk is called
Eulerian if all the edges of ...the embedded graph
G are traversed in this way starting from an arbitrary edge. An embedding that contains an Eulerian straight-ahead walk is called an
Eulerian embedding. In this article, we characterize some properties of Eulerian embeddings of graphs and of embeddings of graphs such that the corresponding medial graph is Eulerian embedded. We prove that in the case of 4-valent planar graphs, the number of straight-ahead walks does not depend on the actual embedding in the plane. Finally, we show that the minimal genus over Eulerian embeddings of a graph can be quite close to the minimal genus over all embeddings.
This book is a very timely exposition of part of an important subject which goes under the general name of "inverse problems". The analogous problem for continuous media has been very much studied, ...with a great deal of difficult mathematics involved, especially partial differential equations. Some of the researchers working on the inverse conductivity problem for continuous media (the problem of recovering the conductivity inside from measurements on the outside) have taken an interest in the authors' analysis of this similar problem for resistor networks.The authors' treatment of inverse problems for electrical networks is at a fairly elementary level. It is accessible to advanced undergraduates, and mathematics students at the graduate level. The topics are of interest to mathematicians working on inverse problems, and possibly to electrical engineers. A few techniques from other areas of mathematics have been brought together in the treatment. It is this amalgamation of such topics as graph theory, medial graphs and matrix algebra, as well as the analogy to inverse problems for partial differential equations, that makes the book both original and interesting.
An i-hedrite is a 4-regular plane graph with faces of size 2, 3 and 4. We do a short survey of their known properties (Deza et al. Proceedings of ICM Satellite Conference On Algebra and ...Combinatorics, 2003b; Deza et al. J Math Res Expo 22:49,2002; Deza and Shtogrin, Polyhedra in Science and Art 11:27, 2003a) and explain some new algorithms that allow their efficient enumeration. Using this we give the symmetry groups of all i-hedrites and the minimal representative for each. We also review the link of 4-hedrites with knot theory and the classification of 4-hedrites with simple central circuits. An i-self-hedrite is a self-dual plane graph with faces and vertices of size/degree 2, 3 and 4. We give a new efficient algorithm for enumerating them based on i-hedrites. We give a classification of their possible symmetry groups and a classification of 4-self-hedrites of symmetry T, Td in terms of the Goldberg-Coxeter construction. Then we give a method for enumerating 4-self-hedrites with simple zigzags.
So far we have studied polynomials and generating functions whose coefficients have a combinatorial significance. In this chapter we take a different view: Given sets S0, S1, S2, . . ., we want to ...determine the counting polynomial f(x) that at x = i gives f(i) = |Si|.
PDF
