I would like to find all graphs or lattices which satisfy the following conditions:

(1) Graph is bipartite with vertex types $A$ and $B$ ($A$-vertices only connected to $B$-vertices and vice-versa)

(2) All edges have coloring either $x$ or $y$, with $x\neq y$

(3) Degree at $A$-vertices: $p = p_x + p_y$, where $p_x$ = number of edges at an $A$-vertex with coloring $x$ and $p_y$ = number of edges with coloring $y$

(4) Degree at $B$-vertices: $q = q_x + q_y$, where $q_x$ = number of edges at a $B$-vertex with coloring $x$ and $q_y$ = number of edges with coloring $y$

(5) Require that $\displaystyle \frac{p_x}{p_y} > 1$, and $\displaystyle \frac{q_x}{q_y} < 1$

Graph may have finite or infinite number of vertices (finite graphs do not need to satisfy the degree requirement on the boundary vertices, but the number of bulk vertices should be $\gg1$)

A special case that can be considered is: $p = q$, $p_x = q_y$, $p_y = q_x$

• Which graphs satisfy conditions (1)–(5)?

From looking at various graphs by hand, the only graph I've found which satisfies these conditions is the Bethe lattice in the infinite case or the Cayley tree in the finite case. Are there others as well?

Some graphs which do not work are the (hyper)cubic lattice, the hexagonal lattice, and the Penrose tiling.

• If the Bethe lattice and Cayley tree are the only graphs which satisfy these conditions, how would one prove that?

New contributor
PartonWavicle is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\begingroup$ I don't understand the "coordination number requirement on the boundary vertices". Can you explain it? $\endgroup$ – Bullet51 May 14 at 15:41
  • $\begingroup$ "Coordination number" means degree, edited question to correct this. To clarify, it means that the vertices on the boundary of the graph do not need to have the same degree as the vertices in the bulk of the graph. For example, the vertices on the boundary of the Cayley tree only have degree 1, regardless of the degree of the bulk vertices. $\endgroup$ – PartonWavicle May 14 at 15:54
  • $\begingroup$ I'm confused what you mean by "cycles can be allowed"; trees are acyclic by definition. $\endgroup$ – PartonWavicle May 14 at 15:56
  • $\begingroup$ How is the boundary defined? What is the boundary of a vertex-transitive cubic graph? $\endgroup$ – Bullet51 May 14 at 15:57
  • $\begingroup$ It means that there exists non-trees satisfying the conditions. $\endgroup$ – Bullet51 May 14 at 15:58

Your Answer

PartonWavicle is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.