Higman–Sims graph (original) (raw)
In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was first constructed by and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, a subgroup of index two in the group of automorphisms of the Higman–Sims graph.
| Property | Value |
|---|---|
| dbo:abstract | In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was first constructed by and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, a subgroup of index two in the group of automorphisms of the Higman–Sims graph. (en) Le graphe de Higman-Sims est, en théorie des graphes, un graphe 22-régulier possédant 100 sommets et 1100 arêtes. (fr) 그래프 이론에서 히그먼-심스 그래프(영어: Higman-Sims graph)는 꼭짓점 100개와 모서리 1100개를 갖는 22-정규 그래프이다. 히그먼-심스 그래프는 이웃한 꼭지점 쌍이 공통 이웃을 공유하지 않고 이웃하지 않은 꼭지점 쌍이 6개의 공통 이웃을 공유하는 유일한 강한 정규 그래프 srg(100,22,0,6)이다. 이것은 에 의해 처음 구성되었고, 1968년에 도널드 G. 히그스과 찰스 C. 심스에 의해 히그먼-심스 그래프의 자기 동형군에서 지표 2인 부분군 을 정의하는 방법으로 재발견되었다. (ko) Граф Хигмана — Симса — это 22-регулярный неориентированный граф со 100 вершинами и 1100 рёбрами. Граф является уникальным сильно регулярным графом srg(100,22,0,6), т.е. никакая соседняя пара вершин не имеет общих соседей и любая несоседняя пара вершин имеет шесть общих соседей. Граф был впервые построен Меснером и был переоткрыт в 1968 Дональдом Дж. Хигманом и Чарльзом Симсом как путь определения и эта группа является подгруппой с индексом два в группе автоморфизмов графа Хигмана — Симса. Построение начинается с графа M22, 77 вершин которого являются блоками S(3,6,22) системы Штейнера W22. Смежные вершины определяются как непересекающиеся блоки. Этот граф является сильно регулярным srg(77,16,0,4), т.е. любая вершина имеет 16 соседей, любые 2 смежные вершины не имеют общих соседей и любые 2 несмежные вершины имеют 4 общих соседа. Этот граф имеет M22:2 в качестве группы автоморфизмов, где M22 является группой Матьё. Граф Хигмана — Симса формируется путём добавления 22 точек W22 и 100-й вершины C. Соседи вершины C определяются как эти 22 точки. Точка смежна блоку тогда и только тогда, когда она принадлежит блоку. Граф Хигмана — Симса можно разбить на две копии графа Хоффмана — Синглтона 352 способами. (ru) No campo da matemática da teoria dos grafos, o Grafo de Higman–Sims é um grafo não direcionado, 22-regular com 100 vértices e 1100 arestas. É o único grafo fortemente regular com 100 vértices e valência 22, onde nenhum par de vértices vizinhos partilham um vizinho comum e cada par de vértices não-vizinhos partilham seis vizinhos comuns. Foi construído em 1968 por Donald G. Higman e Charles C. Sims como uma forma de definir o , e este grupo é um subgrupo do dois no grupo de automorfismos do grafo de Higman–Sims. A construção começa com o grafo M22, cujos 77 vértices são os blocos do S(3,6,22) sistema de Steiner W22. Vértices adjacentes são definidos como blocos disjuntos. Este grafo é fortemente regular; qualquer vértice tem 16 vizinhos, quaisquer dois vértices adjacentes não tem vizinhos comuns, e quaisquer dois vértices não adjacentes têm 4 vizinhos comuns. Este grafo tem M22:2 como seu automorfismo de grupo, sendo M22 o seu . O grafo de Higman–Sims é formado anexando os 22 pontos de W22 e um 100º vértice C. Os vizinhos de C são definidos ser estes 22 pontos. Um ponto adjacente a um bloco é definido ser aquele que está incluído. Um grafo de Higman–Sims pode ser particionado em duas cópias do grafo de Hoffman–Singleton de 352 maneiras. (pt) Граф Гіґмана — Сімса — це 22-регулярний неорієнтований граф зі 100 вершинами і 1100 ребрами. Граф є унікальним сильно регулярним графом srg(100,22,0,6), тобто, ніяка сусідня пара вершин не має спільних сусідів і будь-яка несусідня пара вершин має шість спільних сусідів. Граф уперше побудував Меснер і перевідкрили 1968 року і як шлях визначення і ця група є підгрупою з індексом два в групі автоморфізмів графа Гіґмана — Сімса. Побудова починається з графа M22, 77 вершин якого є блоками S(3,6,22) системи Штейнера W22. Суміжні вершини визначаються як блоки, що не перетинаються. Цей граф сильно регулярний srg(77,16,0,4), тобто, будь-яка вершина має 16 сусідів, будь-які 2 суміжні вершини не мають спільних сусідів і будь-які 2 несуміжні вершини мають 4 спільні сусіди. Цей граф має M22:2 як групу автоморфізмів, де M 22 є . Граф Гіґмана — Сімса формується додаванням 22 точок W22 і 100-ї вершини C. Сусідами вершини C є ці 22 точки. Точка суміжна блоку тоді й лише тоді, коли вона належить блоку. Граф Гіґмана — Сімса можна розбити на дві копії графа Гофмана — Сінглтона 352 способами. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Higman_Sims_Graph.svg?width=300 |
| dbo:wikiPageID | 1110499 (xsd:integer) |
| dbo:wikiPageLength | 7667 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1021876175 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:M22_graph dbr:Regular_graph dbr:Undirected_graph dbr:Donald_G._Higman dbr:Independent_set_(graph_theory) dbr:Index_of_a_subgroup dbr:Integral_graph dbc:Group_theory dbc:Individual_graphs dbc:Regular_graphs dbr:Conway_group dbc:Strongly_regular_graphs dbr:Leech_lattice dbr:Automorphism dbr:Spectral_graph_theory dbr:Cyclic_group dbr:Edge-transitive_graph dbr:Graph_theory dbr:Hamiltonian_graph dbr:Charles_C._Sims dbr:Block_design dbr:Higman–Sims_group dbr:Hoffman–Singleton_graph dbr:Automorphism_group dbr:Semidirect_product dbr:Strongly_regular_graph dbr:XOR dbr:Eulerian_graph dbr:File:Higman-Sims-19.svg dbr:File:Higman_Sims_Graph.svg dbr:File:Higman_Sims_Graph_Parts.svg |
| dbp:automorphisms | 88704000 (xsd:integer) |
| dbp:diameter | 2 (xsd:integer) |
| dbp:edges | 1100 (xsd:integer) |
| dbp:girth | 4 (xsd:integer) |
| dbp:imageCaption | Drawing based on Paul R. Hafner's construction. (en) |
| dbp:name | Higman–Sims graph (en) |
| dbp:namesake | dbr:Donald_G._Higman dbr:Charles_C._Sims |
| dbp:properties | dbr:Edge-transitive_graph dbr:Hamiltonian_graph dbr:Strongly_regular_graph dbr:Eulerian_graph |
| dbp:radius | 2 (xsd:integer) |
| dbp:vertices | 100 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Infobox_graph dbt:Reflist |
| dct:subject | dbc:Group_theory dbc:Individual_graphs dbc:Regular_graphs dbc:Strongly_regular_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:WikicatIndividualGraphs yago:VisualCommunication106873252 yago:WikicatRegularGraphs |
| rdfs:comment | In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was first constructed by and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, a subgroup of index two in the group of automorphisms of the Higman–Sims graph. (en) Le graphe de Higman-Sims est, en théorie des graphes, un graphe 22-régulier possédant 100 sommets et 1100 arêtes. (fr) 그래프 이론에서 히그먼-심스 그래프(영어: Higman-Sims graph)는 꼭짓점 100개와 모서리 1100개를 갖는 22-정규 그래프이다. 히그먼-심스 그래프는 이웃한 꼭지점 쌍이 공통 이웃을 공유하지 않고 이웃하지 않은 꼭지점 쌍이 6개의 공통 이웃을 공유하는 유일한 강한 정규 그래프 srg(100,22,0,6)이다. 이것은 에 의해 처음 구성되었고, 1968년에 도널드 G. 히그스과 찰스 C. 심스에 의해 히그먼-심스 그래프의 자기 동형군에서 지표 2인 부분군 을 정의하는 방법으로 재발견되었다. (ko) No campo da matemática da teoria dos grafos, o Grafo de Higman–Sims é um grafo não direcionado, 22-regular com 100 vértices e 1100 arestas. É o único grafo fortemente regular com 100 vértices e valência 22, onde nenhum par de vértices vizinhos partilham um vizinho comum e cada par de vértices não-vizinhos partilham seis vizinhos comuns. Foi construído em 1968 por Donald G. Higman e Charles C. Sims como uma forma de definir o , e este grupo é um subgrupo do dois no grupo de automorfismos do grafo de Higman–Sims. (pt) Граф Гіґмана — Сімса — це 22-регулярний неорієнтований граф зі 100 вершинами і 1100 ребрами. Граф є унікальним сильно регулярним графом srg(100,22,0,6), тобто, ніяка сусідня пара вершин не має спільних сусідів і будь-яка несусідня пара вершин має шість спільних сусідів. Граф уперше побудував Меснер і перевідкрили 1968 року і як шлях визначення і ця група є підгрупою з індексом два в групі автоморфізмів графа Гіґмана — Сімса. Граф Гіґмана — Сімса можна розбити на дві копії графа Гофмана — Сінглтона 352 способами. (uk) Граф Хигмана — Симса — это 22-регулярный неориентированный граф со 100 вершинами и 1100 рёбрами. Граф является уникальным сильно регулярным графом srg(100,22,0,6), т.е. никакая соседняя пара вершин не имеет общих соседей и любая несоседняя пара вершин имеет шесть общих соседей. Граф был впервые построен Меснером и был переоткрыт в 1968 Дональдом Дж. Хигманом и Чарльзом Симсом как путь определения и эта группа является подгруппой с индексом два в группе автоморфизмов графа Хигмана — Симса. Граф Хигмана — Симса можно разбить на две копии графа Хоффмана — Синглтона 352 способами. (ru) |
| rdfs:label | Higman–Sims graph (en) Graphe de Higman-Sims (fr) 히그먼-심스 그래프 (ko) Grafo de Higman-Sims (pt) Граф Хигмана — Симса (ru) Граф Гіґмана — Сімса (uk) |
| owl:sameAs | freebase:Higman–Sims graph wikidata:Higman–Sims graph dbpedia-fr:Higman–Sims graph dbpedia-ko:Higman–Sims graph dbpedia-pt:Higman–Sims graph dbpedia-ru:Higman–Sims graph dbpedia-uk:Higman–Sims graph https://global.dbpedia.org/id/2tTUh |
| prov:wasDerivedFrom | wikipedia-en:Higman–Sims_graph?oldid=1021876175&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Higman-Sims-19.svg wiki-commons:Special:FilePath/Higman_Sims_Graph.svg wiki-commons:Special:FilePath/Higman_Sims_Graph_Parts.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Higman–Sims_graph |
| is dbo:wikiPageRedirects of | dbr:Higman-Sims_graph |
| is dbo:wikiPageWikiLink of | dbr:M22_graph dbr:Integral_graph dbr:List_of_graphs_by_edges_and_vertices dbr:List_of_mathematical_examples dbr:Gallery_of_named_graphs dbr:Charles_Sims_(mathematician) dbr:Higman–Sims_group dbr:Hoffman–Singleton_graph dbr:Strongly_regular_graph dbr:Symmetric_group dbr:Gewirtz_graph dbr:Higman-Sims_graph |
| is foaf:primaryTopic of | wikipedia-en:Higman–Sims_graph |
