Results 1 to 10 of about 18,037 (258)
On antipodal and diametrical partial cubes
Discussiones Mathematicae Graph Theory, 2021 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Polat Norbert
openaire +2 more sources
Two-Dimensional Partial Cubes [PDF]
The Electronic Journal of Combinatorics, 2020 We investigate the structure of two-dimensional partial cubes, i.e., of isometric subgraphs of hypercubes whose vertex set defines a set family of VC-dimension at most 2. Equivalently, those are the partial cubes which are not contractible to the 3-cube $Q_3$ (here contraction means contracting the edges corresponding to the same coordinate of the ...
Chepoi, Victor +2 more
openaire +2 more sources
Maximal Partial Latin Cubes [PDF]
The Electronic Journal of Combinatorics, 2015 We prove that each maximal partial Latin cube must have more than $29.289\%$ of its cells filled and show by construction that this is a nearly tight bound. We also prove upper and lower bounds on the number of cells containing a fixed symbol in maximal partial Latin cubes and hypercubes, and we use these bounds to determine for small orders $n$ the ...
Britz, Thomas +2 more
openaire +3 more sources
Covering Partial Cubes with Zones [PDF]
The Electronic Journal of Combinatorics, 2014 A partial cube is a graph having an isometric embedding in a hypercube. Partial cubes are characterized by a natural equivalence relation on the edges, whose classes are called zones. The number of zones determines the minimal dimension of a hypercube in which the graph can be embedded. We consider the problem of covering the vertices of a partial cube
Cardinal, Jean, Felsner, Stefan
openaire +3 more sources
Partial Cubes and Crossing Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2002 The reflexive and symmetric Djoković-Winkler relation \(\Theta\) is defined on the edge set of a graph \(G= (V,E)\) in the following way: Edges \(e= xy\) and \(f= uv\), \(x,y,u,v\in V\), are in relation \(\Theta\) if \(d_G(x,u)+ d_G(y,v)\neq d_G(x,v)+ d_G(y,u)\), where the length of a shortest path in \(G\) from \(w\) to \(z\) is denoted by \(d_G(w,z)\)
Klavzar, S, Mulder, Martyn
openaire +3 more sources
Convexity in Partial Cubes: The Hull Number [PDF]
Discrete Mathematics, 2014 19 pages, 4 ...
Albenque, Marie, Knauer, Kolja
openaire +5 more sources
Tribes of cubic partial cubes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 Graphs and Algorithms Partial cubes are graphs isometrically embeddable into hypercubes. Three infinite families and a few sporadic examples of cubic partial cubes are known. The concept of a tribe is introduced as means to systematize the known examples and establish relations among them.
Klavžar, Sandi, Shpectorov, Sergey
openaire +5 more sources
Convex excess in partial cubes [PDF]
Journal of Graph Theory, 2011 AbstractThe convex excess ce(G) of a graph G is introduced as where the summation goes over all convex cycles of G. It is proved that for a partial cube G with n vertices, m edges, and isometric dimension i(G), inequality 2n−m−i(G)−ce(G)≤2 holds. Moreover, the equality holds if and only if the so‐called zone graphs of G are trees.
Klavžar, Sandi, Shpectorov, Sergey
openaire +1 more source
Hypercellular graphs: partial cubes without $Q_3^-$ as partial cube minor
, 2016 We investigate the structure of isometric subgraphs of hypercubes (i.e., partial cubes) which do not contain finite convex subgraphs contractible to the 3-cube minus one vertex $Q^-_3$ (here contraction means contracting the edges corresponding to the same coordinate of the hypercube).
Chepoi, Victor +2 more
openaire +2 more sources