首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Netlike partial cubes III. The median cycle property
Authors:Norbert Polat
Institution:I.A.E., Université Jean Moulin (Lyon 3), 6 cours Albert Thomas, 69355 Lyon Cedex 08, France
Abstract:A graph G has the Median Cycle Property (MCP) if every triple (u0,u1,u2) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if xi is the gate of ui in C, then: {xi,xj}⊆IG(ui,uj) if ij, and dG(xi,xj)<dG(xi,xk)+dG(xk,xj). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K1 by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).
Keywords:Hypercube  Partial cube  Netlike partial cube  Median graph  Even cycle  Benzenoid graph  Cellular bipartite graph  Geodesic convexity  Gated set  Gated amalgamation  Median cycle  Expansion  Pash-Peano space
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号