Netlike partial cubes III. The median cycle property |
| |
Authors: | Norbert Polat |
| |
Affiliation: | 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 i≠j, 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 等数据库收录! |
|