Biregular diagram - Biregular graph

I grafteoretiska matematik , en biregular graf eller semiregular bipartit graf är en tvådelad graf för vilken varje två hörn på samma sida av den givna bidelning ha samma grad som varandra. Om graden av hörn i är och graden av hörn i är , sägs grafen vara -biregular. ${\ displaystyle G = (U, V, E)}$${\ displaystyle U}$${\ displaystyle x}$${\ displaystyle V}$${\ displaystyle y}$${\ displaystyle (x, y)}$

Grafen för den rombiska dodekaedronen är dubbelregelbunden.

Exempel

Varje fullständig bipartitgraf är -biregular. Den rombiska dodecahedronen är ett annat exempel; den är (3,4) -regelbunden. ${\ displaystyle K_ {a, b}}$${\ displaystyle (b, a)}$

Vertex räknas

En -regelbunden graf måste uppfylla ekvationen . Detta följer av ett enkelt dubbelräkningsargument : antalet slutpunkter för kanter i är , antalet slutpunkter för kanter i är , och varje kant bidrar med samma mängd (en) till båda siffrorna. ${\ displaystyle (x, y)}$${\ displaystyle G = (U, V, E)}$${\ displaystyle x | U | = y | V |}$${\ displaystyle U}$${\ displaystyle x | U |}$${\ displaystyle V}$${\ displaystyle y | V |}$

Symmetri

Varje vanlig bipartitgraf är också dubbelregelbunden. Varje kanttransitivt diagram (som inte tillåter grafer med isolerade hörn ) som inte också är vertex-transitivt måste vara dubbelregulärt. I synnerhet är varje kanttransitiv graf antingen vanlig eller dubbelregelbunden.

Konfigurationer

De Levi grafer av geometriska konfigurationer är biregular; en dubbelregelbunden graf är Levi-grafen för en (abstrakt) konfiguration om och endast om dess omkrets är minst sex.

Referenser