Your selections:

9Miller, Mirka
6Ugon, Julien
5Delorme, Charles
5Pérez-Rosés, Hebert
5Yost, David
4Feria-Purón, Ramiro
3Nevo, Eran
3Watters, Paul
2Dekker, Anthony
2Jorgensen, Leif
2Nguyen, Minh Hoang
2Wood, David
1Aloupis, Greg
1Atchison, Rory
1Bui, Hoa
1Doolittle, Joseph
1Gomez, Jose
1Gómez, José
1Herps, Aaron

Show More

Show Less

150101 Pure Mathematics
80802 Computation Theory and Mathematics
7Degree/diameter problem
6Defect
50103 Numerical and Computational Mathematics
4Moore bound
4Moore graphs
30102 Applied Mathematics
3Bipartite Moore graphs
2Bipartite Moore bound
2Botnets
2Compounding of graphs
2Degree-diameter problem
2Degree/diameter problem for bipartite graphs
2F-vector
2Mesh
2Moore bipartite bound
2Moore graph
2Polytope
2Reconstruction

Show More

Show Less

Format Type

On the non-existence of even degree 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:**2007**Type:**Text , Conference paper**Relation:**Paper presented at 18th International Workshop on Combinatorial Algorithms, IWOCA 2007, Rafferty's Resort, Lake Macquarie, New South Wales : 5th-9th November 2007**Full Text:****Description:**Using eigenvalue analysis, it was shown by Erdos et al. that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d2 vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d2-1 vertices do not exist for most values of d, when d is even, and we conjecture that they do not exist for any even d greater than 4.**Description:**2003007893

**Authors:**Miller; Mirka , Nguyen, Minh Hoang , Pineda-Villavicencio, Guillermo**Date:**2007**Type:**Text , Conference paper**Relation:**Paper presented at 18th International Workshop on Combinatorial Algorithms, IWOCA 2007, Rafferty's Resort, Lake Macquarie, New South Wales : 5th-9th November 2007**Full Text:****Description:**Using eigenvalue analysis, it was shown by Erdos et al. that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d2 vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d2-1 vertices do not exist for most values of d, when d is even, and we conjecture that they do not exist for any even d greater than 4.**Description:**2003007893

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.

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

Fitting Voronoi diagrams to planar tesselations

- Aloupis, Greg, Pérez-Rosés, Hebert, Pineda-Villavicencio, Guillermo, Taslakian, Perouz, Trinchet-Almaguer, Dannier

**Authors:**Aloupis, Greg , Pérez-Rosés, Hebert , Pineda-Villavicencio, Guillermo , Taslakian, Perouz , Trinchet-Almaguer, Dannier**Date:**2013**Type:**Text , Conference paper**Relation:**Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 8288 LNCS, p. 349-361**Full Text:****Reviewed:****Description:**Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S 'fits' G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant. © 2013 Springer-Verlag.

**Authors:**Aloupis, Greg , Pérez-Rosés, Hebert , Pineda-Villavicencio, Guillermo , Taslakian, Perouz , Trinchet-Almaguer, Dannier**Date:**2013**Type:**Text , Conference paper**Relation:**Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 8288 LNCS, p. 349-361**Full Text:****Reviewed:****Description:**Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S 'fits' G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant. © 2013 Springer-Verlag.

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

The degree-diameter problem for sparse graph classes

- Pineda-Villavicencio, Guillermo, Wood, David

**Authors:**Pineda-Villavicencio, Guillermo , Wood, David**Date:**2015**Type:**Text , Journal article**Relation:**Electronic Journal of Combinatorics Vol. 22, no. 2 (2015), p. 1-20**Full Text:**false**Reviewed:****Description:**The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree ∆ and diameter k. For fixed k, the answer is

On graphs with cyclic defect or excess

- Delorme, Charles, Pineda-Villavicencio, Guillermo

**Authors:**Delorme, Charles , Pineda-Villavicencio, Guillermo**Date:**2010**Type:**Text , Journal article**Relation:**Electronic Journal of Combinatorics Vol. 17, no. 1 (2010), p.**Full Text:****Reviewed:****Description:**The Moore bound constitutes both an upper bound on the order of a graph of maximum degree d and diameter D = k and a lower bound on the order of a graph of minimum degree d and odd girth g = 2k + 1. Graphs missing or exceeding the Moore bound by Îµ are called graphs with defect or excess Îµ, respectively. While Moore graphs (graphs with Îµ = 0) and graphs with defect or excess 1 have been characterized almost completely, graphs with defect or excess 2 represent a wide unexplored area. Graphs with defect (excess) 2 satisfy the equation G_{d,k}(A) = J_{n}+B (G_{d,k}(A) = J_{n}- B), where A denotes the adjacency matrix of the graph in question, n its order, J_{n}the n Ã— n matrix whose entries are all 1's, B the adjacency matrix of a union of vertex-disjoint cycles, and G_{d,k}(x) a polynomial with integer coefficients such that the matrix G_{d,k}(A) gives the number of paths of length at most k joining each pair of vertices in the graph. In particular, if B is the adjacency matrix of a cycle of order n we call the corresponding graphs graphs with cyclic defect or excess; these graphs are the subject of our attention in this paper. We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of O(64/3 d^{3/2}) for the number of graphs of odd degree d â‰¥ 3 and cyclic defect or excess. This bound is in fact quite generous, and as a way of illustration, we show the non-existence of some families of graphs of odd degree d â‰¥ 3 and cyclic defect or excess. Actually, we conjecture that, apart from the MÃ¶bius ladder on 8 vertices, no non-trivial graph of any degree â‰¥ 3 and cyclic defect or excess exists.

**Authors:**Delorme, Charles , Pineda-Villavicencio, Guillermo**Date:**2010**Type:**Text , Journal article**Relation:**Electronic Journal of Combinatorics Vol. 17, no. 1 (2010), p.**Full Text:****Reviewed:****Description:**The Moore bound constitutes both an upper bound on the order of a graph of maximum degree d and diameter D = k and a lower bound on the order of a graph of minimum degree d and odd girth g = 2k + 1. Graphs missing or exceeding the Moore bound by Îµ are called graphs with defect or excess Îµ, respectively. While Moore graphs (graphs with Îµ = 0) and graphs with defect or excess 1 have been characterized almost completely, graphs with defect or excess 2 represent a wide unexplored area. Graphs with defect (excess) 2 satisfy the equation G_{d,k}(A) = J_{n}+B (G_{d,k}(A) = J_{n}- B), where A denotes the adjacency matrix of the graph in question, n its order, J_{n}the n Ã— n matrix whose entries are all 1's, B the adjacency matrix of a union of vertex-disjoint cycles, and G_{d,k}(x) a polynomial with integer coefficients such that the matrix G_{d,k}(A) gives the number of paths of length at most k joining each pair of vertices in the graph. In particular, if B is the adjacency matrix of a cycle of order n we call the corresponding graphs graphs with cyclic defect or excess; these graphs are the subject of our attention in this paper. We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of O(64/3 d^{3/2}) for the number of graphs of odd degree d â‰¥ 3 and cyclic defect or excess. This bound is in fact quite generous, and as a way of illustration, we show the non-existence of some families of graphs of odd degree d â‰¥ 3 and cyclic defect or excess. Actually, we conjecture that, apart from the MÃ¶bius ladder on 8 vertices, no non-trivial graph of any degree â‰¥ 3 and cyclic defect or excess exists.

On bipartite graphs of defect 2

- Delorme, Charles, Jorgensen, Leif, Miller, Mirka, Pineda-Villavicencio, Guillermo

**Authors:**Delorme, Charles , Jorgensen, Leif , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**European Journal of Combinatorics Vol. 30, no. 4 (2009), p. 798-808**Full Text:****Reviewed:****Description:**It is known that the Moore bipartite bound provides an upper bound on the order of a connected bipartite graph. In this paper we deal with bipartite graphs of maximum degree

**Authors:**Delorme, Charles , Jorgensen, Leif , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**European Journal of Combinatorics Vol. 30, no. 4 (2009), p. 798-808**Full Text:****Reviewed:****Description:**It is known that the Moore bipartite bound provides an upper bound on the order of a connected bipartite graph. In this paper we deal with bipartite graphs of maximum degree

On bipartite graphs of diameter 3 and defect 2

- Delorme, Charles, Jorgensen, Leif, Miller, Mirka, Pineda-Villavicencio, Guillermo

**Authors:**Delorme, Charles , Jorgensen, Leif , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**Journal of Graph Theory Vol. 61, no. 4 (2009), p. 271-288**Full Text:****Reviewed:****Description:**We consider bipartite graphs of degree A<2, diameter D = 3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (â–³,3, -2) -graphs. We prove the uniqueness of the known bipartite (3, 3, -2) -graph and bipartite (4, 3, -2)-graph. We also prove several necessary conditions for the existence of bipartite (â–³,3, -2) - graphs. The most general of these conditions is that either â–³ or â–³-2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when â–³ = 6 and â–³ = 9, we prove the non-existence of the corresponding bipartite (â–³,3,-2)-graphs, thus establishing that there are no bipartite (â–³,3, -2)-graphs, for 5

**Authors:**Delorme, Charles , Jorgensen, Leif , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**Journal of Graph Theory Vol. 61, no. 4 (2009), p. 271-288**Full Text:****Reviewed:****Description:**We consider bipartite graphs of degree A<2, diameter D = 3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (â–³,3, -2) -graphs. We prove the uniqueness of the known bipartite (3, 3, -2) -graph and bipartite (4, 3, -2)-graph. We also prove several necessary conditions for the existence of bipartite (â–³,3, -2) - graphs. The most general of these conditions is that either â–³ or â–³-2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when â–³ = 6 and â–³ = 9, we prove the non-existence of the corresponding bipartite (â–³,3,-2)-graphs, thus establishing that there are no bipartite (â–³,3, -2)-graphs, for 5

Complete catalogue of graphs of maximum degree 3 and defect at most 4

- Miller, Mirka, Pineda-Villavicencio, Guillermo

**Authors:**Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**Discrete Applied Mathematics Vol. 157, no. 13 (2009), p. 2983-2996**Full Text:****Reviewed:****Description:**We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−)-graphs for ≤4. We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−)-graphs with D≥2 and ≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. Copyright Elsevier.

**Authors:**Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Journal article**Relation:**Discrete Applied Mathematics Vol. 157, no. 13 (2009), p. 2983-2996**Full Text:****Reviewed:****Description:**We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−)-graphs for ≤4. We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−)-graphs with D≥2 and ≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. Copyright Elsevier.

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

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 graphs of defect at most 2

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

**Authors:**Feria-Purón, Ramiro , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2011**Type:**Text , Journal article**Relation:**Discrete Applied Mathematics Vol. 159, no. 13 (2011), p. 1331-1344**Full Text:****Reviewed:****Description:**In this paper we consider the degree/diameter problem, namely, given natural numbers Î”<2 and D<1, find the maximum number N(Î”,D) of vertices in a graph of maximum degree Î” and diameter D. In this context, the Moore bound M(Î”,D) represents an upper bound for N(Î”,D). Graphs of maximum degree Î”, diameter D and order M(Î”,D), called Moore graphs, have turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree Î”<2, diameter D<1 and order M(Î”,D)- with small >0, that is, (Î”,D,-)-graphs. The parameter is called the defect. Graphs of defect 1 exist only for Î”=2. When >1, (Î”,D,-)-graphs represent a wide unexplored area. This paper focuses on graphs of defect 2. Building on the approaches developed in Feria-PurÃ³n and Pineda-Villavicencio (2010) [11] we obtain several new important results on this family of graphs. First, we prove that the girth of a (Î”,D,-2)-graph with Î”<4 and D<4 is 2D. Second, and most important, we prove the non-existence of (Î”,D,-2)-graphs with even Î”<4 and D<4; this outcome, together with a proof on the non-existence of (4,3,-2)-graphs (also provided in the paper), allows us to complete the catalogue of (4,D,-)-graphs with D<2 and 0â‰¤â‰¤2. Such a catalogue is only the second census of (Î”,D,-2)-graphs known at present, the first being that of (3,D,-)-graphs with D<2 and 0â‰¤â‰¤2 JÃ¸rgensen (1992) [14]. Other results of this paper include necessary conditions for the existence of (Î”,D,-2)-graphs with odd Î”<5 and D<4, and the non-existence of (Î”,D,-2)-graphs with odd Î”<5 and D<5 such that Î”â‰¡0,2(modD). Finally, we conjecture that there are no (Î”,D,-2)-graphs with Î”<4 and D<4, and comment on some implications of our results for the upper bounds of N(Î”,D). Â© 2011 Elsevier B.V. All rights reserved.

**Authors:**Feria-Purón, Ramiro , Miller, Mirka , Pineda-Villavicencio, Guillermo**Date:**2011**Type:**Text , Journal article**Relation:**Discrete Applied Mathematics Vol. 159, no. 13 (2011), p. 1331-1344**Full Text:****Reviewed:****Description:**In this paper we consider the degree/diameter problem, namely, given natural numbers Î”<2 and D<1, find the maximum number N(Î”,D) of vertices in a graph of maximum degree Î” and diameter D. In this context, the Moore bound M(Î”,D) represents an upper bound for N(Î”,D). Graphs of maximum degree Î”, diameter D and order M(Î”,D), called Moore graphs, have turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree Î”<2, diameter D<1 and order M(Î”,D)- with small >0, that is, (Î”,D,-)-graphs. The parameter is called the defect. Graphs of defect 1 exist only for Î”=2. When >1, (Î”,D,-)-graphs represent a wide unexplored area. This paper focuses on graphs of defect 2. Building on the approaches developed in Feria-PurÃ³n and Pineda-Villavicencio (2010) [11] we obtain several new important results on this family of graphs. First, we prove that the girth of a (Î”,D,-2)-graph with Î”<4 and D<4 is 2D. Second, and most important, we prove the non-existence of (Î”,D,-2)-graphs with even Î”<4 and D<4; this outcome, together with a proof on the non-existence of (4,3,-2)-graphs (also provided in the paper), allows us to complete the catalogue of (4,D,-)-graphs with D<2 and 0â‰¤â‰¤2. Such a catalogue is only the second census of (Î”,D,-2)-graphs known at present, the first being that of (3,D,-)-graphs with D<2 and 0â‰¤â‰¤2 JÃ¸rgensen (1992) [14]. Other results of this paper include necessary conditions for the existence of (Î”,D,-2)-graphs with odd Î”<5 and D<4, and the non-existence of (Î”,D,-2)-graphs with odd Î”<5 and D<5 such that Î”â‰¡0,2(modD). Finally, we conjecture that there are no (Î”,D,-2)-graphs with Î”<4 and D<4, and comment on some implications of our results for the upper bounds of N(Î”,D). Â© 2011 Elsevier B.V. All rights reserved.

The Maximum Degree & Diameter-Bounded Subgraph and its Applications

- Dekker, Anthony, Pérez-Rosés, Hebert, Pineda-Villavicencio, Guillermo, Watters, Paul

**Authors:**Dekker, Anthony , Pérez-Rosés, Hebert , Pineda-Villavicencio, Guillermo , Watters, Paul**Date:**2012**Type:**Text , Journal article**Relation:**Journal of Mathematical Modelling and Algorithms Vol. , no. (2012), p. 1-20**Full Text:**false**Reviewed:****Description:**We introduce the problem of finding the largest subgraph of a given weighted undirected graph (host graph), subject to constraints on the maximum degree and the diameter. We discuss some applications in security, network design and parallel processing, and in connection with the latter we derive some bounds for the order of the largest subgraph in host graphs of practical interest: the mesh and the hypercube. We also present a heuristic strategy to solve the problem, and we prove an approximation ratio for the algorithm. Finally, we provide some experimental results with a variety of host networks, which show that the algorithm performs better in practice than the prediction provided by our theoretical approximation ratio. © 2012 Springer Science+Business Media B.V.

Topology of interconnection networks with given degree and diameter

- Pineda-Villavicencio, Guillermo

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Thesis , PhD**Full Text:****Description:**Doctor of Philosophy

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2009**Type:**Text , Thesis , PhD**Full Text:****Description:**Doctor of Philosophy

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.

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

New largest known graphs of diameter 6

- Pineda-Villavicencio, Guillermo, Gómez, José, Miller, Mirka, Pérez-Rosés, Hebert

**Authors:**Pineda-Villavicencio, Guillermo , Gómez, José , Miller, Mirka , Pérez-Rosés, Hebert**Date:**2009**Type:**Text , Journal article**Relation:**Networks Vol. 53, no. 4 (2009), p. 315-328**Full Text:****Reviewed:****Description:**In the pursuit of obtaining largest graphs of given maximum degree**Description:**2003007890

**Authors:**Pineda-Villavicencio, Guillermo , Gómez, José , Miller, Mirka , Pérez-Rosés, Hebert**Date:**2009**Type:**Text , Journal article**Relation:**Networks Vol. 53, no. 4 (2009), p. 315-328**Full Text:****Reviewed:****Description:**In the pursuit of obtaining largest graphs of given maximum degree**Description:**2003007890

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

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