Lee Township, Brown County, Illinois and Table of the largest known graphs of a given diameter and maximal degree: Difference between pages
(Difference between pages)
Content deleted Content added
Expansion |
|||
Line 1: | Line 1: | ||
==Table of the orders of the largest known graphs for the undirected Degree Diameter problem== |
|||
{{Infobox Settlement |
|||
Below is the table of the best known graphs (as of October 2008) in the undirected [[Degree diameter problem]] for graphs of [[Degree (graph theory)|degree]] at most 3≤<math>d</math>≤16 and [[Distance (graph theory)|diameter]] 2≤<math>k</math>≤10. Only a few of the graphs in this table are known to be optimal (marked in bold) and thus, finding a larger graph that is closer in order (in terms of the size of the vertex set) to the [[Moore graph|Moore bound]] is considered an [[Open problem|open problem]]. Some general constructions are known for values of <math>d</math> and <math>k</math> outside the range shown in the table. |
|||
|official_name = Lee Township |
|||
<center> |
|||
|settlement_type = [[Civil township|Township]] |
|||
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;" |
|||
|nickname = |
|||
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10''' |
|||
|motto = |
|||
|- |
|||
| '''3''' || style="background-color: red;" | '''10''' ||style="background-color: blue;" | '''20''' ||style="background-color: blue;" | '''38''' ||style="background-color: #66cc66;" | 70 ||style="background-color: #ffff00;" | 132 ||style="background-color: #ffff00;" | 196 ||style="background-color: #ffff00;" | 336 ||style="background-color: #ffff00;" | 600 ||style="background-color: #ffcc99;" | 1250 |
|||
|- |
|||
| '''4''' ||style="background-color: blue;" | '''15''' ||style="background-color: #999900;" | 41 ||style="background-color: #ffff00;" | 96 || 364 ||style="background-color: #666666;" | 740 ||style="background-color: #FF9900;" | 1 320 ||style="background-color: #FF9900;" | 3 243 ||style="background-color: #FF9900;" | 7 575 ||style="background-color: #FF9900;" | 17 703 |
|||
<!-- Images --> |
|||
|- |
|||
|image_skyline = |
|||
| '''5''' ||style="background-color: blue;" | '''24''' ||style="background-color: #ffff00;" | 72 ||style="background-color: #bbffff;" | 210 ||style="background-color: #FF9900;" | 624 ||style="background-color: #00ff7f;" | 2 772 ||style="background-color: #FF9900;" | 5 516 ||style="background-color: #FF9900;" | 17 030 ||style="background-color: #FF9900;" | 57 840 ||style="background-color: #FF9900;" | 187 056 |
|||
|imagesize = |
|||
|- |
|||
|image_caption = |
|||
| '''6''' ||style="background-color: #336666;" | '''32''' ||style="background-color: #ffff00;" | 110 ||style="background-color: #FF9900;" | 390 ||style="background-color: #FF9900;" | 1404 ||style="background-color: #00ff7f;" | 7 917 ||style="background-color: #FF9900;" | 19 383 ||style="background-color: #FF9900;" | 76 461 ||style="background-color: #FF9900;" | 307 845 ||style="background-color: #FF9900;" | 1 253 615 |
|||
|image_flag = |
|||
|- |
|||
|image_seal = |
|||
| '''7''' ||style="background-color: red;" | '''50''' ||style="background-color: #ffff00;" | 168 ||style="background-color: #bbffff;" | 672 ||style="background-color: #FF0066;" | 2 756 ||style="background-color: #FF9900;" | 11 988 ||style="background-color: #FF9900;" | 52 768 ||style="background-color: #FF9900;" | 249 660 ||style="background-color: #FF9900;" | 1 223 050 ||style="background-color: #FF9900;" | 6 007 230 |
|||
|- |
|||
| '''8''' || 57 ||style="background-color: #993300;" | 253 ||style="background-color: #FF9900;" | 1 100 ||style="background-color: #FF9900;" | 5 060 ||style="background-color: #666633;" | 39 672 ||style="background-color: #FF9900;" | 131 137 ||style="background-color: #FF9900;" | 734 820 ||style="background-color: #FF9900;" | 4 243 100 ||style="background-color: #FF9900;" | 24 897 161 |
|||
|- |
|||
| '''9''' || 74 || 585 ||style="background-color: #FF9900;" | 1 550 ||style="background-color: #FF9900;" | 8 200 ||style="background-color: #00ff7f;" | 75 893 ||style="background-color: #FF9900;" | 279 616 ||style="background-color: #FF9900;" | 1 686 600 ||style="background-color: #FF9900;" | 12 123 288 ||style="background-color: #FF9900;" | 65 866 350 |
|||
|- |
|||
| '''10''' || 91 || 650 ||style="background-color: #FF9900;" | 2 286 ||style="background-color: #FF9900;" | 13 140 ||style="background-color: #666633;" | 134 690 ||style="background-color: #FF9900;" | 583 083 ||style="background-color: #FF9900;" | 4 293 452 ||style="background-color: #FF9900;" | 27 997 191 ||style="background-color: #FF9900;" | 201 038 922 |
|||
|- |
|||
| '''11''' ||style="background-color: #ffff00;" | 104 || 715 || 3 200 ||style="background-color: #FF9900;" | 19 500 || 156 864 ||style="background-color: #FF9900;" | 1 001 268 ||style="background-color: #FF9900;" | 7 442 328 || style="background-color: #FF9900;" | 72 933 102 ||style="background-color: #FF9900;" | 600 380 000 |
|||
|- |
|||
| '''12''' || 133 ||style="background-color: #666633;" | 786 || 4 680 ||style="background-color: #FF9900;" | 29 470||style="background-color: #00ff7f;" | 359 772 ||style="background-color: #FF9900;" | 1 999 500 ||style="background-color: #FF9900;" | 15 924 326 ||style="background-color: #FF9900;" | 158 158 875 ||style="background-color: #FF9900;" | 1 506 252 500 |
|||
|- |
|||
| '''13''' ||style="background-color: #ff99ff;" | 162 ||style="background-color: #666633;" | 851 || 6 560 ||style="background-color: #FF9900;" |40 260 || 531 440 ||style="background-color: #FF9900;" | 3 322 080 ||style="background-color: #FF9900;" | 29 927 790 ||style="background-color: #FF9900;" | 249 155 760 ||style="background-color: #FF9900;" | 3 077 200 700 |
|||
|- |
|||
| '''14''' || 183 ||style="background-color: #666633;" | 916 || 8 200 ||style="background-color: #FF9900;" | 57 837 ||style="background-color: #00ff7f;" | 816 294 || 6 200 460 ||style="background-color: #FF9900;" | 55 913 932 ||style="background-color: #FF9900;" | 600 123 780 ||style="background-color: #FF9900;" | 7 041 746 081 |
|||
|- |
|||
| '''15''' || 186 || 1 215 || 11 712 ||style="background-color: #FF9900;" | 76 518 || 1 417 248 ||style="background-color: #FF9900;" | 8 599 986 ||style="background-color: #FF9900;" | 90 001 236 ||style="background-color: #FF9900;" | 1 171 998 164 ||style="background-color: #FF9900;" | 10 012 349 898 |
|||
|- |
|||
| '''16''' ||style="background-color: #ffff00;" | 198 || 1 600 || 14 640 || 132 496 || 1 771 560 || 14 882 658 ||style="background-color: #FF9900;" | 140 559 416 ||style="background-color: #FF9900;" | 2 025 125 476 ||style="background-color: #FF9900;" | 12 951 451 931 |
|||
|} |
|||
</center> |
|||
<!-- Maps --> |
|||
|image_map = Map highlighting Lee Township, Brown County, Illinois.svg |
|||
|mapsize = |
|||
|map_caption = Location in Brown County |
|||
|image_map1 = |
|||
|mapsize1 = |
|||
|map_caption1 = |
|||
The following table is the key to the colors in the table presented above: |
|||
<!-- Location --> |
|||
|subdivision_type = [[List of countries|Country]] |
|||
|subdivision_name = [[United States]] |
|||
|subdivision_type1 = [[Political divisions of the United States|State]] |
|||
|subdivision_name1 = [[Illinois]] |
|||
|subdivision_type2 = [[List of counties in Illinois|County]] |
|||
|subdivision_name2 = [[Brown County, Illinois|Brown]] |
|||
|government_footnotes = |
|||
|government_type = |
|||
|leader_title = |
|||
|leader_name = |
|||
|leader_title1 = |
|||
|leader_name1 = |
|||
|established_title = Established |
|||
|established_date = [[November 8]], [[1853]] |
|||
<!-- Area --> |
|||
|area_footnotes = |
|||
|area_magnitude = |
|||
|area_total_km2 = 97.44 |
|||
|area_land_km2 = 97.33 |
|||
|area_water_km2 = 0.11 |
|||
|area_total_sq_mi = 37.62 |
|||
|area_land_sq_mi = 37.58 |
|||
|area_water_sq_mi = 0.04 |
|||
|area_water_percent = 0.11 |
|||
<center> |
|||
<!-- Population --> |
|||
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;" |
|||
|population_as_of = [[United States Census, 2000|2000]] |
|||
|'''Color''' || style="text-align: center;" |'''Details''' |
|||
|population_footnotes = |
|||
|- |
|||
|population_total = 342 |
|||
|style="background-color: red; text-align: center;" | * || The [[Petersen graph|Petersen]] and [[Hoffman–Singleton graph|Hoffman–Singleton]] graphs. |
|||
|population_density_km2 = 3.5 |
|||
|- |
|||
|population_density_sq_mi = 9.1 |
|||
|style="background-color: blue; text-align: center;" | * || Other non Moore but optimal graphs. |
|||
|- |
|||
|style="background-color: #999900; text-align: center;" | * || Graph found by James Allwright. |
|||
|- |
|||
|style="background-color: #336666; text-align: center;" | * || Graph found by G. Wegner. |
|||
|- |
|||
|style="background-color: #ffff00; text-align: center;" | * || Graphs found by Geoffrey Exoo. |
|||
|- |
|||
|style="background-color: #ff99ff; text-align: center;" | * || Family of graphs found by Brendan D. McKay, Mirka Miller and Jozef Širáň. More details are available in a paper by the authors. |
|||
|- |
|||
|style="background-color: #666633; text-align: center;" | * || Graphs found by J. Gómez. |
|||
|- |
|||
|style="background-color: #993300; text-align: center;" | * || Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels. |
|||
|- |
|||
|style="background-color: #66cc66; text-align: center;" | * || Graph found by Fiol, M.A. and Yebra, J.L.A. |
|||
|- |
|||
|style="background-color: #666666; text-align: center;" | * || Graph found by Francesc Comellas and J. Gómez. |
|||
|- |
|||
|style="background-color: #00ff7f; text-align: center;" | * || Graphs found by G. Pineda-Villavicencio, J. Gómez, Mirka Miller and H. Pérez-Rosés. More details are available in a paper by the authors. |
|||
|- |
|||
|style="background-color: #FF9900; text-align: center;" | * || Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň. |
|||
|- |
|||
|style="background-color: #bbffff; text-align: center;" | * || Graphs found by Michael Sampels. |
|||
|- |
|||
|style="background-color: #FF0066; text-align: center;" | * || Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors. |
|||
|- |
|||
|style="background-color: #ffcc99; text-align: center;" | * || Graph found by Marston Conder. |
|||
|} |
|||
</center> |
|||
<!-- General information --> |
|||
|elevation_footnotes = |
|||
|elevation_m = 222 |
|||
|elevation_ft = 728 |
|||
|latd = 39 |
|||
|latm = 58 |
|||
|lats = 30 |
|||
|latNS = N |
|||
|longd = 9 |
|||
|longm = 51 |
|||
|longs = 01 |
|||
|longEW = W |
|||
<!-- Area/postal codes & others --> |
|||
|timezone = [[North American Central Time Zone|CST]] |
|||
|utc_offset = -6 |
|||
|timezone_DST = [[North American Central Time Zone|CDT]] |
|||
|utc_offset_DST = -5 |
|||
|postal_code_type = ZIP codes |
|||
|postal_code = 62353, 62375 |
|||
|area_code = |
|||
|blank_name = [[Geographic Names Information System|GNIS]] feature ID |
|||
|blank_info = [http://geonames.usgs.gov/pls/gnispublic/f?p=gnispq:3:::NO::P3_FID:0429239 0429239] |
|||
|website = |
|||
|footnotes = |
|||
}} |
|||
==References== |
|||
'''Lee Township''' is one of nine [[Civil township|townships]] in [[Brown County, Illinois|Brown County]], [[Illinois]], [[United States|USA]]. As of the [[United States Census, 2000|2000 census]], its population was 342<ref>[http://factfinder.census.gov/servlet/DTTable?_bm=y&-context=dt&-ds_name=DEC_2000_SF1_U&-mt_name=DEC_2000_SF1_U_P001&-CONTEXT=dt&-tree_id=4001&-all_geo_types=N&-geo_id=06000US1700942561&-search_results=01000US&-format=&-_lang=en United States Census Bureau American FactFinder]</ref>. |
|||
* {{citation |
|||
| last1 = Hoffman |
|||
| first1 = Alan J. |
|||
| last2 = Singleton |
|||
| first2 = Robert R. |
|||
| title = Moore graphs with diameter 2 and 3 |
|||
| journal = IBM Journal of Research and Development |
|||
| volume = 5 |
|||
| issue = 4 |
|||
| year = 1960 |
|||
| pages = 497–504 |
|||
| url = http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf |
|||
| id = {{MathSciNet | id = 0140437}}}} |
|||
* {{citation |
|||
==Geography== |
|||
| last1 = J. Dinneen |
|||
According to the [[United States Census Bureau]], Lee Township covers an area of 37.62 square miles (97.44 square kilometers); of this, 0.04 square miles (0.11 square kilometers) or 0.11 percent is water. |
|||
| first1 = Michael |
|||
| last2 = Hafner |
|||
| first2 = Paul R. |
|||
| title = New Results for the Degree/Diameter Problem |
|||
| journal = Networks |
|||
| volume = 24 |
|||
| issue = 7 |
|||
| year = 1994 |
|||
| pages = 359-367 |
|||
| url = http://arxiv.org/PS_cache/math/pdf/9504/9504214v1.pdf}} |
|||
* {{citation |
|||
===Cities=== |
|||
| last1 = McKay |
|||
* [[Mound Station, Illinois|Mound Station]] |
|||
| first1 = Brendan D. |
|||
| last2 = Miller |
|||
| first2 = Mirka |
|||
| last3 = Širáň |
|||
| first3 = Jozef |
|||
| title = A note on large graphs of diameter two and given maximum degree |
|||
| journal = Journal of Combinatorial Theory Series B |
|||
| volume = 74 |
|||
| issue = 4 |
|||
| year = 1998 |
|||
| pages = 110-118 |
|||
| url = http://portal.acm.org/citation.cfm?id=299331}} |
|||
* {{citation |
|||
===Unincorporated towns=== |
|||
| last1 = Miller |
|||
* [[Buckhorn, Illinois|Buckhorn]] |
|||
| first1 = Mirka |
|||
* [[Fargo, Illinois|Fargo]] |
|||
| last2 = Širáň |
|||
* [[Timewell, Illinois|Timewell]] |
|||
| first2 = Jozef |
|||
| title = Moore graphs and beyond: A survey of the degree/diameter problem |
|||
| journal = Electronic Journal of Combinatorics |
|||
| volume = Dynamic survey D |
|||
| year = 2005 |
|||
| url = http://www.combinatorics.org/Surveys/ds14.ps}} |
|||
* {{citation |
|||
===Adjacent townships=== |
|||
| last1 = Pineda-Villavicencioa |
|||
* [[Pea Ridge Township, Brown County, Illinois|Pea Ridge Township]] (north) |
|||
| first1 = Guillermo |
|||
* [[Mount Sterling Township, Brown County, Illinois|Mount Sterling Township]] (east) |
|||
| last2 = Gómez |
|||
* [[Elkhorn Township, Brown County, Illinois|Elkhorn Township]] (southeast) |
|||
| first2 = José |
|||
* [[Buckhorn Township, Brown County, Illinois|Buckhorn Township]] (south) |
|||
| last3 = Miller |
|||
* [[Concord Township, Adams County, Illinois|Concord Township, Adams County]] (west) |
|||
| first3 = Mirka |
|||
* [[Clayton Township, Adams County, Illinois|Clayton Township, Adams County]] (northwest) |
|||
| last4 = Pérez-Rosésd |
|||
| first4 = Hebert |
|||
| title = New Largest Graphs of Diameter 6 |
|||
| journal = Electronic Notes in Discrete Mathematics |
|||
| volume = 24 |
|||
| year = 2006 |
|||
| pages = 153-160}} |
|||
* {{citation |
|||
===Cemeteries=== |
|||
| last1 = Loz |
|||
The township contains these seven cemeteries: Ausmus, Buckhorn, Cleaves, Fargo, Howe, Lee and Orton. |
|||
| first1 = Eyal |
|||
| last2 = Širáň |
|||
===Major highways=== |
|||
| first2 = Jozef |
|||
* [[Image:US 24.svg|25px]] [[US Route 24]] |
|||
| title = New record graphs in the degree-diameter problem |
|||
| journal = Australasian Journal of Combinatorics |
|||
===Airports and landing strips=== |
|||
| volume = 41 |
|||
* Brown County Flyers Association Airport |
|||
| year = 2008 |
|||
* Mayfield Landing Strip |
|||
| pages = 63-80 |
|||
| url = http://ajc.maths.uq.edu.au/volume_contents.php3?vol=41}} |
|||
==School districts== |
|||
* Brown County Community Unit School District 1 |
|||
==Political districts== |
|||
* [[Illinois' 18th congressional district]] |
|||
* State House District 93 |
|||
* State Senate District 47 |
|||
==References== |
|||
* [http://www.census.gov/geo/www/tiger/tgrshp2007/tgrshp2007.html United States Census Bureau 2007 TIGER/Line Shapefiles] |
|||
* [http://geonames.usgs.gov/domestic/ United States Board on Geographic Names (GNIS)] |
|||
* [http://www.nationalatlas.gov/ United States National Atlas] |
|||
<references/> |
|||
==External links== |
==External links== |
||
* [http://www-mat.upc.es/grup_de_grafs/ Degree Diameter] online table. |
|||
* [http://www.city-data.com/township/Lee-Brown-IL.html City-Data.com] |
|||
* [http://moorebound.indstate.edu/index.php/Main_Page Degree Diameter] self-update wiki. |
|||
* [http://www.cyberdriveillinois.com/departments/archives/irad/brown.html Illinois State Archives] |
|||
* [http://www.eyal.tk/degreediameter/ Eyal Loz's] Degree-Diameter problem page. |
|||
* [http://isu.indstate.edu/ge/DD/index.html Geoffrey Exoo's] Degree-Diameter record graphs page. |
|||
{{Brown County, Illinois}} |
|||
[[Category:Townships in Brown County, Illinois]] |
Revision as of 07:27, 13 October 2008
Table of the orders of the largest known graphs for the undirected Degree Diameter problem
Below is the table of the best known graphs (as of October 2008) in the undirected Degree diameter problem for graphs of degree at most 3≤≤16 and diameter 2≤≤10. Only a few of the graphs in this table are known to be optimal (marked in bold) and thus, finding a larger graph that is closer in order (in terms of the size of the vertex set) to the Moore bound is considered an open problem. Some general constructions are known for values of and outside the range shown in the table.
\ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
3 | 10 | 20 | 38 | 70 | 132 | 196 | 336 | 600 | 1250 |
4 | 15 | 41 | 96 | 364 | 740 | 1 320 | 3 243 | 7 575 | 17 703 |
5 | 24 | 72 | 210 | 624 | 2 772 | 5 516 | 17 030 | 57 840 | 187 056 |
6 | 32 | 110 | 390 | 1404 | 7 917 | 19 383 | 76 461 | 307 845 | 1 253 615 |
7 | 50 | 168 | 672 | 2 756 | 11 988 | 52 768 | 249 660 | 1 223 050 | 6 007 230 |
8 | 57 | 253 | 1 100 | 5 060 | 39 672 | 131 137 | 734 820 | 4 243 100 | 24 897 161 |
9 | 74 | 585 | 1 550 | 8 200 | 75 893 | 279 616 | 1 686 600 | 12 123 288 | 65 866 350 |
10 | 91 | 650 | 2 286 | 13 140 | 134 690 | 583 083 | 4 293 452 | 27 997 191 | 201 038 922 |
11 | 104 | 715 | 3 200 | 19 500 | 156 864 | 1 001 268 | 7 442 328 | 72 933 102 | 600 380 000 |
12 | 133 | 786 | 4 680 | 29 470 | 359 772 | 1 999 500 | 15 924 326 | 158 158 875 | 1 506 252 500 |
13 | 162 | 851 | 6 560 | 40 260 | 531 440 | 3 322 080 | 29 927 790 | 249 155 760 | 3 077 200 700 |
14 | 183 | 916 | 8 200 | 57 837 | 816 294 | 6 200 460 | 55 913 932 | 600 123 780 | 7 041 746 081 |
15 | 186 | 1 215 | 11 712 | 76 518 | 1 417 248 | 8 599 986 | 90 001 236 | 1 171 998 164 | 10 012 349 898 |
16 | 198 | 1 600 | 14 640 | 132 496 | 1 771 560 | 14 882 658 | 140 559 416 | 2 025 125 476 | 12 951 451 931 |
The following table is the key to the colors in the table presented above:
Color | Details |
* | The Petersen and Hoffman–Singleton graphs. |
* | Other non Moore but optimal graphs. |
* | Graph found by James Allwright. |
* | Graph found by G. Wegner. |
* | Graphs found by Geoffrey Exoo. |
* | Family of graphs found by Brendan D. McKay, Mirka Miller and Jozef Širáň. More details are available in a paper by the authors. |
* | Graphs found by J. Gómez. |
* | Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels. |
* | Graph found by Fiol, M.A. and Yebra, J.L.A. |
* | Graph found by Francesc Comellas and J. Gómez. |
* | Graphs found by G. Pineda-Villavicencio, J. Gómez, Mirka Miller and H. Pérez-Rosés. More details are available in a paper by the authors. |
* | Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň. |
* | Graphs found by Michael Sampels. |
* | Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors. |
* | Graph found by Marston Conder. |
References
- Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, MR0140437
- J. Dinneen, Michael; Hafner, Paul R. (1994), "New Results for the Degree/Diameter Problem" (PDF), Networks, 24 (7): 359–367
- McKay, Brendan D.; Miller, Mirka; Širáň, Jozef (1998), "A note on large graphs of diameter two and given maximum degree", Journal of Combinatorial Theory Series B, 74 (4): 110–118
- Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics, Dynamic survey D
- Pineda-Villavicencioa, Guillermo; Gómez, José; Miller, Mirka; Pérez-Rosésd, Hebert (2006), "New Largest Graphs of Diameter 6", Electronic Notes in Discrete Mathematics, 24: 153–160
- Loz, Eyal; Širáň, Jozef (2008), "New record graphs in the degree-diameter problem", Australasian Journal of Combinatorics, 41: 63–80
External links
- Degree Diameter online table.
- Degree Diameter self-update wiki.
- Eyal Loz's Degree-Diameter problem page.
- Geoffrey Exoo's Degree-Diameter record graphs page.