An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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
dbo:wikiPageID
  • 59938063 (xsd:integer)
dbo:wikiPageLength
  • 20260 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1037226083 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
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
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is dbp:properties of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License