Your selections:

3Defect
20101 Pure Mathematics
2Degree/diameter problem for bipartite graphs
2Repeat
10102 Applied Mathematics
10802 Computation Theory and Mathematics
1Bipartite Moore bound
1Combinatorics
1Degree/diameter problem
1Engineering design
1Graphic methods
1Large bipartite graphs
1Maximum degree
1Moore bipartite bound
1Moore bipartite graph
1Moore bound
1Moore graph
1Natural number
1Upper bound

Show More

Show Less

Format Type

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.

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

- «
- ‹
- 1
- ›
- »

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