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

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

Show More

Show Less

Format Type

A new proof of Balinski's theorem on the connectivity of polytopes

- Pineda-Villavicencio, Guillermo

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2021**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 344, no. 7 (2021), p.**Full Text:****Reviewed:****Description:**Balinski (1961) proved that the graph of a d-dimensional convex polytope is d-connected. We provide a new proof of this result. Our proof provides details on the nature of a separating set with exactly d vertices; some of which appear to be new. © 2021 Elsevier B.V.

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2021**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 344, no. 7 (2021), p.**Full Text:****Reviewed:****Description:**Balinski (1961) proved that the graph of a d-dimensional convex polytope is d-connected. We provide a new proof of this result. Our proof provides details on the nature of a separating set with exactly d vertices; some of which appear to be new. © 2021 Elsevier B.V.

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. http://purl.org/au-research/grants/arc/DP180100602**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. http://purl.org/au-research/grants/arc/DP180100602**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.

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.

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.

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

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

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.

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.

Measuring Surveillance in Online Advertising: A Big Data Approach

- Herps, Aaron, Watters, Paul, Pineda-Villavicencio, Guillermo

**Authors:**Herps, Aaron , Watters, Paul , Pineda-Villavicencio, Guillermo**Date:**2013**Type:**Text , Conference paper**Relation:**Proceedings - 4th Cybercrime and Trustworthy Computing Workshop, CTC 2013 p. 30-35**Full Text:**false**Reviewed:****Description:**There is an increasing public and policy awareness that tracking cookies are being used to support behavioral advertising, but the extent to which tracking is occurring is not clear. The extent of tracking could have implications for the enforceability of legislative responses to the sharing of personal data, including the Privacy Act 1988 (Cth). In this paper, we develop a methodology for determining the prevalence of tracking cookies, and report the results for a sample of the 50 most visited sites by Australians. We find that the use of tracking cookies is endemic, but that distinct clusters of tracking can be identified across categories including search, pornography and social networking. The implications of the work in relation to privacy are discussed.

New benchmarks for large-scale networks with given maximum degree and diameter

- Loz, Eyal, Pineda-Villavicencio, Guillermo

**Authors:**Loz, Eyal , Pineda-Villavicencio, Guillermo**Date:**2010**Type:**Text , Journal article**Relation:**Computer Journal Vol. 53, no. 7 (2010), p. 1092-1105**Full Text:**false**Reviewed:****Description:**Large-scale networks have become ubiquitous elements of our society. Modern social networks, supported by communication and travel technology, have grown in size and complexity to unprecedented scales. Computer networks, such as the Internet, have a fundamental impact on commerce, politics and culture. The study of networks is also central in biology, chemistry and other natural sciences. Unifying aspects of these networks are a small maximum degree and a small diameter, which are also shared by many network models, such as small-world networks. Graph theoretical methodologies can be instrumental in the challenging task of predicting, constructing and studying the properties of large-scale networks. This task is now necessitated by the vulnerability of large networks to phenomena such as cross-continental spread of disease and botnets (networks of malware). In this article, we produce the new largest known networks of maximum degree 17 ≤ ∆ ≤ 20 and diameter 2 ≤ D ≤ 10, using a wide range of techniques and concepts, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. In this way, we provide new benchmarks for networks with given maximum degree and diameter, and a complete overview of state-of-the-art methodology that can be used to construct such networks.

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

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

Non-existence of bipartite graphs of diameter at least 4 and defect 2

- Pineda-Villavicencio, Guillermo

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2011**Type:**Text , Journal article**Relation:**Journal of Algebraic Combinatorics Vol. 34, no. 2 (2011), p. 163-182**Full Text:****Reviewed:****Description:**The Moore bipartite bound represents an upper bound on the order of a bipartite graph of maximum degree Î” and diameter D. Bipartite graphs of maximum degree Î”, diameter D and order equal to the Moore bipartite bound are called Moore bipartite graphs. Such bipartite graphs exist only if D=2,3,4 and 6, and for D=3,4,6, they have been constructed only for those values of Î” such that Î”-1 is a prime power. The scarcity of Moore bipartite graphs, together with the applications of such large topologies in the design of interconnection networks, prompted us to investigate what happens when the order of bipartite graphs misses the Moore bipartite bound by a small number of vertices. In this direction the first class of graphs to be studied is naturally the class of bipartite graphs of maximum degree Î”, diameter D, and two vertices less than the Moore bipartite bound (defect 2), that is, bipartite (Î”,D,-2)-graphs. For Î”â‰¥3 bipartite (Î”,2,-2)-graphs are the complete bipartite graphs with partite sets of orders Î” and Î”-2. In this paper we consider bipartite (Î”,D,-2)-graphs for Î”â‰¥3 and Dâ‰¥3. Some necessary conditions for the existence of bipartite (Î”,3,-2)-graphs for Î”â‰¥3 are already known, as well as the non-existence of bipartite (Î”,D,-2)-graphs with Î”â‰¥3 and D=4,5,6,8. Furthermore, it had been conjectured that bipartite (Î”,D,-2)-graphs for Î”â‰¥3 and Dâ‰¥4 do not exist. Here, using graph spectra techniques, we completely settle this conjecture by proving the non-existence of bipartite (Î”,D,-2)-graphs for all Î”â‰¥3 and all Dâ‰¥6. Â© 2010 Springer Science+Business Media, LLC.

**Authors:**Pineda-Villavicencio, Guillermo**Date:**2011**Type:**Text , Journal article**Relation:**Journal of Algebraic Combinatorics Vol. 34, no. 2 (2011), p. 163-182**Full Text:****Reviewed:****Description:**The Moore bipartite bound represents an upper bound on the order of a bipartite graph of maximum degree Î” and diameter D. Bipartite graphs of maximum degree Î”, diameter D and order equal to the Moore bipartite bound are called Moore bipartite graphs. Such bipartite graphs exist only if D=2,3,4 and 6, and for D=3,4,6, they have been constructed only for those values of Î” such that Î”-1 is a prime power. The scarcity of Moore bipartite graphs, together with the applications of such large topologies in the design of interconnection networks, prompted us to investigate what happens when the order of bipartite graphs misses the Moore bipartite bound by a small number of vertices. In this direction the first class of graphs to be studied is naturally the class of bipartite graphs of maximum degree Î”, diameter D, and two vertices less than the Moore bipartite bound (defect 2), that is, bipartite (Î”,D,-2)-graphs. For Î”â‰¥3 bipartite (Î”,2,-2)-graphs are the complete bipartite graphs with partite sets of orders Î” and Î”-2. In this paper we consider bipartite (Î”,D,-2)-graphs for Î”â‰¥3 and Dâ‰¥3. Some necessary conditions for the existence of bipartite (Î”,3,-2)-graphs for Î”â‰¥3 are already known, as well as the non-existence of bipartite (Î”,D,-2)-graphs with Î”â‰¥3 and D=4,5,6,8. Furthermore, it had been conjectured that bipartite (Î”,D,-2)-graphs for Î”â‰¥3 and Dâ‰¥4 do not exist. Here, using graph spectra techniques, we completely settle this conjecture by proving the non-existence of bipartite (Î”,D,-2)-graphs for all Î”â‰¥3 and all Dâ‰¥6. Â© 2010 Springer Science+Business Media, LLC.

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 defect at most 4

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

**Authors:**Feria-Purón, Ramiro , Pineda-Villavicencio, Guillermo**Date:**2011**Type:**Text , Journal article**Relation:**Discrete Applied Mathematics Vol.160, no.1-2 (2011), p.140-154**Full Text:****Reviewed:****Description:**We consider the bipartite version of the degree/diameter problem, namely, given natural numbers Î” â‰¥ 2 and D â‰¥ 2, find the maximum number Nb (Î”, D) of vertices in a bipartite graph of maximum degree Î” and diameter D. In this context, the Moore bipartite bound Mb (Î”, D) represents an upper bound for Nb (Î”, D). Bipartite graphs of maximum degree Î”, diameter D and order Mb (Î”, D)-called Moore bipartite graphs-have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree Î” â‰¥ 2, diameter D â‰¥ 2 and order Mb (Î”, D) - Îµ{lunate} with small Îµ{lunate} > 0, that is, bipartite (Î”, D, - Îµ{lunate})-graphs. The parameter Îµ{lunate} is called the defect. This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if Î” â‰¥ 3 and D â‰¥ 3, they may only exist for D = 3. However, when Îµ{lunate} > 2 bipartite (Î”, D, - Îµ{lunate})-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite (Î”, D, - 4)-graphs; the complete catalogue of bipartite (3, D, - Îµ{lunate})-graphs with D â‰¥ 2 and 0 â‰¤ Îµ{lunate} â‰¤ 4; the complete catalogue of bipartite (Î”, D, - Îµ{lunate})-graphs with Î” â‰¥ 2, 5 â‰¤ D â‰¤ 187 (D â‰ 6) and 0 â‰¤ Îµ{lunate} â‰¤ 4; a proof of the non-existence of all bipartite (Î”, D, - 4)-graphs with Î” â‰¥ 3 and odd D â‰¥ 5. Finally, we conjecture that there are no bipartite graphs of defect 4 for Î” â‰¥ 3 and D â‰¥ 5, and comment on some implications of our results for the upper bounds of Nb (Î”, D). Â© 2011 Elsevier B.V. All rights reserved.

**Authors:**Feria-Purón, Ramiro , Pineda-Villavicencio, Guillermo**Date:**2011**Type:**Text , Journal article**Relation:**Discrete Applied Mathematics Vol.160, no.1-2 (2011), p.140-154**Full Text:****Reviewed:****Description:**We consider the bipartite version of the degree/diameter problem, namely, given natural numbers Î” â‰¥ 2 and D â‰¥ 2, find the maximum number Nb (Î”, D) of vertices in a bipartite graph of maximum degree Î” and diameter D. In this context, the Moore bipartite bound Mb (Î”, D) represents an upper bound for Nb (Î”, D). Bipartite graphs of maximum degree Î”, diameter D and order Mb (Î”, D)-called Moore bipartite graphs-have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree Î” â‰¥ 2, diameter D â‰¥ 2 and order Mb (Î”, D) - Îµ{lunate} with small Îµ{lunate} > 0, that is, bipartite (Î”, D, - Îµ{lunate})-graphs. The parameter Îµ{lunate} is called the defect. This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if Î” â‰¥ 3 and D â‰¥ 3, they may only exist for D = 3. However, when Îµ{lunate} > 2 bipartite (Î”, D, - Îµ{lunate})-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite (Î”, D, - 4)-graphs; the complete catalogue of bipartite (3, D, - Îµ{lunate})-graphs with D â‰¥ 2 and 0 â‰¤ Îµ{lunate} â‰¤ 4; the complete catalogue of bipartite (Î”, D, - Îµ{lunate})-graphs with Î” â‰¥ 2, 5 â‰¤ D â‰¤ 187 (D â‰ 6) and 0 â‰¤ Îµ{lunate} â‰¤ 4; a proof of the non-existence of all bipartite (Î”, D, - 4)-graphs with Î” â‰¥ 3 and odd D â‰¥ 5. Finally, we conjecture that there are no bipartite graphs of defect 4 for Î” â‰¥ 3 and D â‰¥ 5, and comment on some implications of our results for the upper bounds of Nb (Î”, D). Â© 2011 Elsevier B.V. All rights reserved.

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

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.

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

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 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

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