#### Local equivalence of directed graphs and monadic second-order logic = 유향그래프의 국지적 동등과 단항 이차 논리

Cited 0 time in Cited 0 time in
• Hit : 205
For a simple directed graph \$\It{F}\$ if there is an arc from \$\It{x}\$ to \$\It{y}\$ for a pair \$\It{x}\$, \$\It{y}\$ of distinct vertices, then we call \$\It{x}\$ an \$\It{inneighbor}\$ of \$\It{y}\$ and conversely \$\It{y}\$ an \$\It{outneighbor}\$ of \$\It{x}\$. To locally complement F at a vertex v is for each inneighbor x and outneighbor y of v, to delete the arc (x, y) if there is an arc from \$\It{x}\$ to \$\It{y}\$, or to add an arc from x to y otherwise. We say that a directed graph \$\It{F}\$ is \$\It{locally equvalent}\$ to another directed graph \$\It{H}\$ if \$\It{H}\$ is obtained from F by successive local complementations. Furthermore a directed graph \$\It{H}\$ is a \$\It{vertex-minor}\$ of F if H can be obtained by applying a sequence of local complementations and deletions of vertices to \$\It{F}\$. A. Bouchet introduced Eulerian systems which are related to directed graphs and shows that a pair of directed graphs \$\It{F}\$, H have same Eulerian system if and only if \$\It{H}\$ is locally equivalent to F. We show that vertex-minor relation can be expressed in modulo-2 counting monadic second-order logic. This generalizes known properties of local complementations and vertex-minors of undirected graphs to directed graphs.
Oum, Sang-Ilresearcher엄상일researcher
Description
한국과학기술원 : 수리과학과,
Publisher
한국과학기술원
Issue Date
2010
Identifier
455185/325007  / 020084129
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 수리과학과, 2010.08, [ iii, 20 p. ]

Keywords

vertex-minor; monadic second-order logic; local equivalence; directed graphs; eulerian systems; 오일러리안 시스템; 꼭지점마이너; 단항 이차 논리; 국지적 동등; 유향그래프

URI
http://hdl.handle.net/10203/42235