Locally linear graph (original) (raw)
In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Many constructions for locally linear graphs are known. Examples of locally linear graphs include the triangular cactus graphs, the line graphs of 3-regular triangle-free graphs, and the Cartesian products of smaller locally linear graphs. Certain Kneser graphs, and certain strongly regular graphs, are also locally linear. The question of how many edges locally linear graphs can have is one of the formulations of the Ruzsa–Szemerédi problem. Although dense graphs can have a number of edges proportional to the square of the number of vertices, locally linear graphs have a smaller number of edges, falling short of the square by at least a small non-constant factor. The densest planar graphs that can be locally linear are also known. The least dense locally linear graphs are the triangular cactus graphs. (en) Локально линейный граф — неориентированный граф в окрестности каждой вершины . То есть для любой вершины любая окрестность должна быть смежной в точности ещё одной вершине, соседней вершине . Эквивалентно, любое ребро такого графа принадлежит единственному треугольнику . Локально линейные графы называются также локально паросочетаемыми графами. Примеры локально линейных графов включают треугольные кактусы, рёберные графы 3-регулярных графов без треугольников и прямое произведение более мелких локально линейных графов. Определённые кнезеровские графы, и некоторые сильно регулярные графы также локально линейны. Некоторые локально линейные графы имеют почти квадратичное число рёбер. Вопрос, как плотны эти графы, может быть одной из формулировок Проблема Ружи – Семереди. Известны также наиболее плотные планарные графы, которые могут быть локально линейными. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Paley9-unique-triangle.svg?width=300 |
| dbo:wikiPageID | 59938063 (xsd:integer) |
| dbo:wikiPageLength | 20260 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1037226083 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Euler's_polyhedral_formula dbr:Berlekamp–van_Lint–Seidel_graph dbr:Binomial_coefficient dbr:Bipartite_half dbr:Dense_graph dbc:Graph_families dbr:Little_o_notation dbr:Regular_graph dbr:Cubic_graph dbr:Cubic_surface dbr:Cuboctahedron dbr:Undirected_graph dbr:Degree_(graph_theory) dbr:Induced_matching dbr:Petersen_graph dbr:Clique-sum dbr:Endre_Szemerédi dbr:Friendship_graph dbr:Conway's_99-graph_problem dbr:Line_graph dbr:Cactus_graph dbr:Cage_(graph_theory) dbr:Big_Omega_notation dbr:Clique_(graph_theory) dbr:Complement_graph dbr:Triangle-free_graph dbr:Distance-regular_graph dbr:Games_graph dbr:3-3_duoprism dbr:Brouwer–Haemers_graph dbr:Foster_graph dbr:Graph_theory dbr:Hamming_graph dbr:Intersection_graph dbr:Arithmetic_progression dbr:John_Horton_Conway dbr:Big_O_notation dbr:Salem–Spencer_set dbr:Planar_graph dbr:Imre_Z._Ruzsa dbr:Kneser_graph dbr:Neighborhood_(graph_theory) dbr:Cartesian_product_of_graphs dbr:Strongly_regular_graph dbr:Utility_graph dbr:Schläfli_graph dbr:Ruzsa–Szemerédi_problem dbr:Polyhedral_graph dbr:Paley_graph dbr:Triangular_cactus_graph dbr:Square_antiprism dbr:Disjoint_set dbr:Tripartite_graph dbr:File:Cuboctahedron.jpg dbr:File:Friendship_graphs.svg dbr:Cossidente–Penttila_graph dbr:File:Dense_planar_locally_linear.svg dbr:File:Paley9-unique-triangle.svg |
| dbp:wikiPageUsesTemplate | dbt:Main dbt:R dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_families |
| rdfs:comment | In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. (en) Локально линейный граф — неориентированный граф в окрестности каждой вершины . То есть для любой вершины любая окрестность должна быть смежной в точности ещё одной вершине, соседней вершине . Эквивалентно, любое ребро такого графа принадлежит единственному треугольнику . Локально линейные графы называются также локально паросочетаемыми графами. Некоторые локально линейные графы имеют почти квадратичное число рёбер. Вопрос, как плотны эти графы, может быть одной из формулировок Проблема Ружи – Семереди. Известны также наиболее плотные планарные графы, которые могут быть локально линейными. (ru) |
| rdfs:label | Locally linear graph (en) Локально линейный граф (ru) Локально лінійний граф (uk) |
| owl:sameAs | wikidata:Locally linear graph dbpedia-ru:Locally linear graph dbpedia-uk:Locally linear graph https://global.dbpedia.org/id/9P97w |
| prov:wasDerivedFrom | wikipedia-en:Locally_linear_graph?oldid=1037226083&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Cuboctahedron.jpg wiki-commons:Special:FilePath/Friendship_graphs.svg wiki-commons:Special:FilePath/Dense_planar_locally_linear.svg wiki-commons:Special:FilePath/Paley9-unique-triangle.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Locally_linear_graph |
| is dbo:wikiPageWikiLink of | dbr:Bipartite_half dbr:Cuboctahedron dbr:Induced_matching dbr:Neighbourhood_(graph_theory) dbr:Friendship_graph dbr:Graph_removal_lemma dbr:Conway's_99-graph_problem dbr:Berlekamp–Van_Lint–Seidel_graph dbr:Cactus_graph dbr:Games_graph dbr:3-3_duoprism dbr:Brouwer–Haemers_graph dbr:Foster_graph dbr:Salem–Spencer_set dbr:Cap_set dbr:Strongly_regular_graph dbr:Schläfli_graph dbr:Ruzsa–Szemerédi_problem dbr:Paley_graph dbr:Tripod_packing |
| is dbp:properties of | dbr:Cuboctahedron dbr:Friendship_graph dbr:Brouwer–Haemers_graph |
| is foaf:primaryTopic of | wikipedia-en:Locally_linear_graph |
