Examples of products giving large graphs with given degree and diameter (Q1199421): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q195165
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / author
 
Property / author: Charles Delorme / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Large Graphs with Given Degree and Diameter III / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3852212 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Decomposition of Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5592263 / rank
 
Normal rank

Latest revision as of 15:15, 16 May 2024

scientific article
Language Label Description Also known as
English
Examples of products giving large graphs with given degree and diameter
scientific article

    Statements

    Examples of products giving large graphs with given degree and diameter (English)
    0 references
    16 January 1993
    0 references
    Let \(G=(V_ 1,E_ 1)\) and \(H=(V_ 2,E_ 2)\) be finite undirected graphs, and let \(\varphi\) be an automorphism of \(H\). Let the edges of \(G\) be oriented in some way: let \(\vec E_ 1\) denote the set of ordered pairs which are the directed edges of the resulting directed graph. The product \(G*_ \varphi H\) is an undirected graph defined in terms of this orientation of \(G\). \[ V(G*_ \varphi H)=V(G)\times V(H); \] \[ E(G*_ \varphi H)=\bigl\{(g,h)(g,h'): hh'\in E_ 2\bigr\}\cup\bigl\{(g,h)(g',\varphi(h)): gg'\in\vec E_ 1\bigr\}. \] ``We can say that we build a product of \(G\) with a half of \(H\). (...) Of course, a change in the orientation of \(G\) modifies the resulting \(G*_ \varphi H\). (...) In the following most calculations will give an upper bound for the diameter that holds for any orientation in \(G\). Hence we do not recall the orientation in the notation \(*_ \varphi\).'' This product is applied to give some constructions giving large graphs with given degree and diameter.
    0 references
    products of graphs
    0 references
    Moore bound
    0 references
    diameter
    0 references
    degree
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references