Biregular graf - Biregular graph

v graficko-teoretická matematika, a biregular graph^[1] nebo semiregular bipartite graph^[2] je bipartitní graf ${ displaystyle G = (U, V, E)}$ pro které mají každé dva vrcholy na stejné straně dané bipartice stejné stupeň jako každý jiný. Pokud je stupeň vrcholů v ${ displaystyle U}$ je ${ displaystyle x}$ a stupeň vrcholů v ${ displaystyle V}$ je ${ displaystyle y}$, pak se říká, že graf je ${ displaystyle (x, y)}$-biregular.

Graf kosočtverečný dvanáctistěn je biregular.

Příklad

Každý kompletní bipartitní graf ${ displaystyle K_ {a, b}}$ je ${ displaystyle (b, a)}$-biregular.^[3]The kosočtverečný dvanáctistěn je dalším příkladem; je (3,4) -biregular.^[4]

Počítá se vrchol

An ${ displaystyle (x, y)}$-biregular graf ${ displaystyle G = (U, V, E)}$ musí vyhovovat rovnici ${ displaystyle x | U | = y | V |}$. To vyplývá z jednoduchého argument dvojího počítání: počet koncových bodů hran v ${ displaystyle U}$ je ${ displaystyle x | U |}$, počet koncových bodů hran v ${ displaystyle V}$ je ${ displaystyle y | V |}$a každá hrana přispívá stejnou částkou (jedna) k oběma číslům.

Symetrie

Každý pravidelný bipartitní graf je také biregular.Every hranový tranzitivní graf (zakazující grafy s izolované vrcholy ) to také není vrchol-tranzitivní musí být biregular.^[3] Zejména každý hranový přechodový graf je buď pravidelný, nebo biregulární.

Konfigurace

The Grafy Levi z geometrické konfigurace jsou biregular; biregular graph is a Levi graph of an (abstract) configuration if and only if its obvod je nejméně šest.^[5]

Reference