Your selections:

50802 Computation Theory and Mathematics
30103 Numerical and Computational Mathematics
20102 Applied Mathematics
2Degree/diameter problem
2F-vector
2Polytope
1Almost simplicial polytope
1Bipartite Moore bound
1Bipartite Moore graphs
1Combinatorics
1Compounding of graphs
1Connectivity
1Continuant
1Cube
1Cubical polytope
1Defect
1Degree-diameter problem
1Degree/diameter problem for bipartite graphs
1Diameter 2 and defect

Show More

Show Less

Format Type

Almost simplicial polytopes : the lower and upper bound theorems

- Nevo, Eran, Pineda-Villavicencio, Guillermo, Ugon, Julien, Yost, David

**Authors:**Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2020**Type:**Text , Journal article**Relation:**Canadian Journal of Mathematics Vol. 72, no. 2 (2020), p. 537-556**Full Text:****Reviewed:****Description:**We study -vertex -dimensional polytopes with at most one nonsimplex facet with, say, vertices, called almost simplicial polytopes. We provide tight lower and upper bound theorems for these polytopes as functions of, and, thus generalizing the classical Lower Bound Theorem by Barnette and the Upper Bound Theorem by McMullen, which treat the case where s = 0. We characterize the minimizers and provide examples of maximizers for any. Our construction of maximizers is a generalization of cyclic polytopes, based on a suitable variation of the moment curve, and is of independent interest. © 2018 Canadian Mathematical Society.

**Authors:**Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2020**Type:**Text , Journal article**Relation:**Canadian Journal of Mathematics Vol. 72, no. 2 (2020), p. 537-556**Full Text:****Reviewed:****Description:**We study -vertex -dimensional polytopes with at most one nonsimplex facet with, say, vertices, called almost simplicial polytopes. We provide tight lower and upper bound theorems for these polytopes as functions of, and, thus generalizing the classical Lower Bound Theorem by Barnette and the Upper Bound Theorem by McMullen, which treat the case where s = 0. We characterize the minimizers and provide examples of maximizers for any. Our construction of maximizers is a generalization of cyclic polytopes, based on a suitable variation of the moment curve, and is of independent interest. © 2018 Canadian Mathematical Society.

Connectivity of cubical polytopes

- Bui, Hoa, Pineda-Villavicencio, Guillermo, Ugon, Julien

**Authors:**Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien**Date:**2019**Type:**Text , Journal article**Relation:**Journal of Combinatorial Theory Series A Vol. 169, no. (Jan 2019), p. 21**Full Text:****Reviewed:****Description:**A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.

**Authors:**Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien**Date:**2019**Type:**Text , Journal article**Relation:**Journal of Combinatorial Theory Series A Vol. 169, no. (Jan 2019), p. 21**Full Text:****Reviewed:****Description:**A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.

Lower bound theorems for general polytopes

- Pineda-Villavicencio, Guillermo, Ugon, Julien, Yost, David

**Authors:**Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2019**Type:**Text , Journal article**Relation:**European Journal of Combinatorics Vol. 79, no. (2019), p. 27-45**Full Text:****Reviewed:****Description:**For a d-dimensional polytope with v vertices, d + 1 <= v <= 2d, we calculate precisely the minimum possible number of m-dimensional faces, when m = 1 or m >= 0.62d. This confirms a conjecture of Grunbaum, for these values of m. For v = 2d + 1, we solve the same problem when m = 1 or d - 2; the solution was already known for m = d - 1. In all these cases, we give a characterisation of the minimising polytopes. We also show that there are many gaps in the possible number of m-faces: for example, there is no polytope with 80 edges in dimension 10, and a polytope with 407 edges can have dimension at most 23.

**Authors:**Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2019**Type:**Text , Journal article**Relation:**European Journal of Combinatorics Vol. 79, no. (2019), p. 27-45**Full Text:****Reviewed:****Description:**For a d-dimensional polytope with v vertices, d + 1 <= v <= 2d, we calculate precisely the minimum possible number of m-dimensional faces, when m = 1 or m >= 0.62d. This confirms a conjecture of Grunbaum, for these values of m. For v = 2d + 1, we solve the same problem when m = 1 or d - 2; the solution was already known for m = d - 1. In all these cases, we give a characterisation of the minimising polytopes. We also show that there are many gaps in the possible number of m-faces: for example, there is no polytope with 80 edges in dimension 10, and a polytope with 407 edges can have dimension at most 23.

On the reconstruction of polytopes

- Doolittle, Joseph, Nevo, Eran, Pineda-Villavicencio, Guillermo, Ugon, Julien, Yost, David

**Authors:**Doolittle, Joseph , Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2019**Type:**Text , Journal article**Relation:**Discrete and Computational Geometry Vol. 61, no. 2 (2019), p. 285-302**Full Text:****Reviewed:****Description:**Blind and Mani, and later Kalai, showed that the face lattice of a simple polytope is determined by its graph, namely its 1-skeleton. Call a vertex of a d-polytope nonsimple if the number of edges incident to it is more than d. We show that (1) the face lattice of any d-polytope with at most two nonsimple vertices is determined by its 1-skeleton; (2) the face lattice of any d-polytope with at most d- 2 nonsimple vertices is determined by its 2-skeleton; and (3) for any d> 3 there are two d-polytopes with d- 1 nonsimple vertices, isomorphic (d- 3) -skeleta and nonisomorphic face lattices. In particular, the result (1) is best possible for 4-polytopes. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

**Authors:**Doolittle, Joseph , Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2019**Type:**Text , Journal article**Relation:**Discrete and Computational Geometry Vol. 61, no. 2 (2019), p. 285-302**Full Text:****Reviewed:****Description:**Blind and Mani, and later Kalai, showed that the face lattice of a simple polytope is determined by its graph, namely its 1-skeleton. Call a vertex of a d-polytope nonsimple if the number of edges incident to it is more than d. We show that (1) the face lattice of any d-polytope with at most two nonsimple vertices is determined by its 1-skeleton; (2) the face lattice of any d-polytope with at most d- 2 nonsimple vertices is determined by its 2-skeleton; and (3) for any d> 3 there are two d-polytopes with d- 1 nonsimple vertices, isomorphic (d- 3) -skeleta and nonisomorphic face lattices. In particular, the result (1) is best possible for 4-polytopes. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

The excess degree of a polytope

- Pineda-Villavicencio, Guillermo, Ugon, Julien, Yost, David

**Authors:**Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2018**Type:**Text , Journal article**Relation:**SIAM Journal on Discrete Mathematics Vol. 32, no. 3 (2018), p. 2011-2046**Full Text:****Reviewed:****Description:**We define the excess degree \xi (P) of a d-polytope P as 2f1 - df0, where f0 and f1 denote the number of vertices and edges, respectively. This parameter measures how much P deviates from being simple. It turns out that the excess degree of a d-polytope does not take every natural number: the smallest possible values are 0 and d - 2, and the value d - 1 only occurs when d = 3 or 5. On the other hand, for fixed d, the number of values not taken by the excess degree is finite if d is odd, and the number of even values not taken by the excess degree is finite if d is even. The excess degree is then applied in three different settings. First, it is used to show that polytopes with small excess (i.e., \xi (P) < d) have a very particular structure: provided d \not = 5, either there is a unique nonsimple vertex, or every nonsimple vertex has degree d + 1. This implies that such polytopes behave in a similar manner to simple polytopes in terms of Minkowski decomposability: they are either decomposable or pyramidal, and their duals are always indecomposable. Second, we characterize completely the decomposable d-polytopes with 2d + 1 vertices (up to combinatorial equivalence). Third, all pairs (f0, f1), for which there exists a 5-polytope with f0 vertices and f1 edges, are determined.

**Authors:**Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David**Date:**2018**Type:**Text , Journal article**Relation:**SIAM Journal on Discrete Mathematics Vol. 32, no. 3 (2018), p. 2011-2046**Full Text:****Reviewed:****Description:**We define the excess degree \xi (P) of a d-polytope P as 2f1 - df0, where f0 and f1 denote the number of vertices and edges, respectively. This parameter measures how much P deviates from being simple. It turns out that the excess degree of a d-polytope does not take every natural number: the smallest possible values are 0 and d - 2, and the value d - 1 only occurs when d = 3 or 5. On the other hand, for fixed d, the number of values not taken by the excess degree is finite if d is odd, and the number of even values not taken by the excess degree is finite if d is even. The excess degree is then applied in three different settings. First, it is used to show that polytopes with small excess (i.e., \xi (P) < d) have a very particular structure: provided d \not = 5, either there is a unique nonsimple vertex, or every nonsimple vertex has degree d + 1. This implies that such polytopes behave in a similar manner to simple polytopes in terms of Minkowski decomposability: they are either decomposable or pyramidal, and their duals are always indecomposable. Second, we characterize completely the decomposable d-polytopes with 2d + 1 vertices (up to combinatorial equivalence). Third, all pairs (f0, f1), for which there exists a 5-polytope with f0 vertices and f1 edges, are determined.

On the maximum order of graphs embedded in surfaces

- Nevo, Eran, Pineda-Villavicencio, Guillermo, Wood, David

**Authors:**Nevo, Eran , Pineda-Villavicencio, Guillermo , Wood, David**Date:**2016**Type:**Text , Journal article**Relation:**Journal of Combinatorial Theory. Series B Vol. 119, no. (2016), p. 28-41**Full Text:****Reviewed:****Description:**The maximum number of vertices in a graph of maximum degree

**Authors:**Nevo, Eran , Pineda-Villavicencio, Guillermo , Wood, David**Date:**2016**Type:**Text , Journal article**Relation:**Journal of Combinatorial Theory. Series B Vol. 119, no. (2016), p. 28-41**Full Text:****Reviewed:****Description:**The maximum number of vertices in a graph of maximum degree

Continuants and some decompositions into squares

- Delorme, Charles, Pineda-Villavicencio, Guillermo

**Authors:**Delorme, Charles , Pineda-Villavicencio, Guillermo**Date:**2015**Type:**Text , Journal article**Relation:**Integers Vol. 15, no. (2015), p. 1**Full Text:****Reviewed:****Description:**In 1855 H. J. S. Smith proved Fermat's two-square using the notion of palindromic continuants. In his paper, Smith constructed a proper representation of a prime number

**Authors:**Delorme, Charles , Pineda-Villavicencio, Guillermo**Date:**2015**Type:**Text , Journal article**Relation:**Integers Vol. 15, no. (2015), p. 1**Full Text:****Reviewed:****Description:**In 1855 H. J. S. Smith proved Fermat's two-square using the notion of palindromic continuants. In his paper, Smith constructed a proper representation of a prime number

Quadratic form representations via generalized continuants

- Delorme, Charles, Pineda-Villavicencio, Guillermo

**Authors:**Delorme, Charles , Pineda-Villavicencio, Guillermo**Date:**2015**Type:**Text , Journal article**Relation:**Journal of Integer Sequences Vol. 18, no. 6 (2015), p. Article number 15.6.4**Full Text:**false**Reviewed:****Description:**H. J. S. Smith proved Fermat’s two-square theorem using the notion of palindromic continuants. In this paper we extend Smith’s approach to proper binary quadratic form representations in some commutative Euclidean rings, including rings of integers and rings of polynomials over fields of odd characteristic. Also, we present new deterministic algorithms for finding the corresponding proper representations. © 2015 University of Waterloo. All rights reserved.

Constructions of large graphs on surfaces

- Feria-Purón, Ramiro, Pineda-Villavicencio, Guillermo

**Authors:**Feria-Purón, Ramiro , Pineda-Villavicencio, Guillermo**Date:**2014**Type:**Text , Journal article**Relation:**Graphs and Combinatorics Vol. 30, no. 4 (2014), p. 895-908**Full Text:**false**Reviewed:****Description:**We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface

On large bipartite graphs of diameter 3

- Feria-Purón, Ramiro, Miller, Mirka, Pineda-Villavicencio, Guillermo

**Authors:**Feria-Purón, Ramiro , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2013**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 313, no. 4 (2013), p. 381-390**Relation:**http://purl.org/au-research/grants/arc/DP110102011**Full Text:****Reviewed:****Description:**We consider the bipartite version of the degree/diameter problem, namely, given natural numbers dâ‰¥2 and Dâ‰¥2, find the maximum number N b(d,D) of vertices in a bipartite graph of maximum degree d and diameter D. In this context, the bipartite Moore bound Mb(d,D) represents a general upper bound for Nb(d,D). Bipartite graphs of order Mb(d,D) are very rare, and determining Nb(d,D) still remains an open problem for most (d,D) pairs. This paper is a follow-up of our earlier paper (Feria-PurÃ³n and Pineda-Villavicencio, 2012 [5]), where a study on bipartite (d,D,-4)-graphs (that is, bipartite graphs of order M b(d,D)-4) was carried out. Here we first present some structural properties of bipartite (d,3,-4)-graphs, and later prove that there are no bipartite (7,3,-4)-graphs. This result implies that the known bipartite (7,3,-6)-graph is optimal, and therefore Nb(7,3)=80. We dub this graph the Hafner-Loz graph after its first discoverers Paul Hafner and Eyal Loz. The approach here presented also provides a proof of the uniqueness of the known bipartite (5,3,-4)-graph, and the non-existence of bipartite (6,3,-4)-graphs. In addition, we discover at least one new largest known bipartite-and also vertex-transitive-graph of degree 11, diameter 3 and order 190, a result which improves by four vertices the previous lower bound for Nb(11,3). © 2012 Elsevier B.V. All rights reserved.**Description:**2003011037

**Authors:**Feria-Purón, Ramiro , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2013**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 313, no. 4 (2013), p. 381-390**Relation:**http://purl.org/au-research/grants/arc/DP110102011**Full Text:****Reviewed:****Description:**We consider the bipartite version of the degree/diameter problem, namely, given natural numbers dâ‰¥2 and Dâ‰¥2, find the maximum number N b(d,D) of vertices in a bipartite graph of maximum degree d and diameter D. In this context, the bipartite Moore bound Mb(d,D) represents a general upper bound for Nb(d,D). Bipartite graphs of order Mb(d,D) are very rare, and determining Nb(d,D) still remains an open problem for most (d,D) pairs. This paper is a follow-up of our earlier paper (Feria-PurÃ³n and Pineda-Villavicencio, 2012 [5]), where a study on bipartite (d,D,-4)-graphs (that is, bipartite graphs of order M b(d,D)-4) was carried out. Here we first present some structural properties of bipartite (d,3,-4)-graphs, and later prove that there are no bipartite (7,3,-4)-graphs. This result implies that the known bipartite (7,3,-6)-graph is optimal, and therefore Nb(7,3)=80. We dub this graph the Hafner-Loz graph after its first discoverers Paul Hafner and Eyal Loz. The approach here presented also provides a proof of the uniqueness of the known bipartite (5,3,-4)-graph, and the non-existence of bipartite (6,3,-4)-graphs. In addition, we discover at least one new largest known bipartite-and also vertex-transitive-graph of degree 11, diameter 3 and order 190, a result which improves by four vertices the previous lower bound for Nb(11,3). © 2012 Elsevier B.V. All rights reserved.**Description:**2003011037

Topology of interconnection networks with given degree and diameter

- Pineda-Villavicencio, Guillermo

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2010**Type:**Text , Journal article**Relation:**Bulletin of the Australian Mathematical Society Vol. 81, no. 2 (2010), p. 350-352**Full Text:****Reviewed:**

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2010**Type:**Text , Journal article**Relation:**Bulletin of the Australian Mathematical Society Vol. 81, no. 2 (2010), p. 350-352**Full Text:****Reviewed:**

On the nonexistence of graphs of diameter 2 and defect 2

- Miller, Mirka, Nguyen, Minh Hoang, Pineda-Villavicencio, Guillermo

**Authors:**Miller, Mirka , Nguyen, Minh Hoang , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**The Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, no. (2009), p. 5-20**Full Text:**false**Reviewed:****Description:**In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d² + 1 vertices), and found that such graphs exist only for d = 2; 3; 7 and possibly 57. In 1980, Erdös et al., using eigenvalue analysis, showed that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d² vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d² - 1 vertices do not exist for most values of d with d ≥ 6, and conjecture that they do not exist for any d ≥ 6.**Description:**2003007893

On graphs of maximum degree 3 and defect 4

- Pineda-Villavicencio, Guillermo, Miller, Mirka

**Authors:**Pineda-Villavicencio, Guillermo , Miller, Mirka**Date:**2008**Type:**Text , Journal article**Relation:**Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008), p. 25-31**Full Text:**false**Reviewed:****Description:**It is well known that apart from the Petersen graph there are no Moore graphs of degree 3. As a cubic graph must have an even number of vertices, there are no graphs of maximum degree 3 and

New largest graphs of diameter 6. (Extended Abstract)

- Pineda-Villavicencio, Guillermo, Gomez, Jose, Miller, Mirka, Pérez-Rosés, Hebert

**Authors:**Pineda-Villavicencio, Guillermo , Gomez, Jose , Miller, Mirka , Pérez-Rosés, Hebert**Date:**2006**Type:**Text , Journal article**Relation:**Electronic Notes in Discrete Mathematics Vol. 24, no. (2006), p. 153-160**Full Text:****Reviewed:****Description:**In the pursuit of obtaining largest graphs of given degree and diameter, many construction techniques have arisen. Compounding of graphs is one such technique. In this paper, by means of the compounding of complete graphs into the bipartite Moore graph of diameter 6, we obtain two families of (**Description:**C1

- «
- ‹
- 1
- ›
- »

Are you sure you would like to clear your session, including search history and login status?