3
$\begingroup$

Consider a (simple undirected) graph $G$ with set of vertices $V=A\cup B$ with $|B|=30$.

(1) Every vertex in $A$ has an edge to exactly $3$ vertices in $B$.

(2) Every vertex in $B$ has an edge to exactly $4$ other vertices in $B$.

(3) For any two vertices in $B$ connected by an edge, some vertex in $A$ is connected to both of them.

What is the minimum size of $A$?

--

The number of edges in $B$ is $2|B|=60$. The number of edges between $A$ and $B$ is $3|A|$. Condition (3) implies that for each of the $60$ edges in $B$, some vertex in $A$ is connected to both endpoints of the edge. Since every vertex in $A$ is connected to $3$ vertices in $B$ (hence also $3$ pairs of vertices), $|A|\geq 20$.

Is this the optimal bound, and if so, how can we construct an example?

$\endgroup$
4
$\begingroup$

Every vertex of $A$ covers 3 vertices of $B$, and at most covers 3 pairs of edges forming a triangle. So, to reach the lower bound of $|A|=20$, it suffices that $B$ is a $4$-regular in $30$ vertices such that its edges can be partitioned in triangles.

Using this condition, doodling a bit in a piece of paper we reach this graph: Graph that can be edge-disjointly covered by triangles.

It can be covered by 10 edge-disjoint triangles. It's not 4-regular, but taking two disjoint copies and identifying the vertex of degree 2 we reach a graph with the desired conditions.

$\endgroup$
  • 1
    $\begingroup$ I believe your graph is the $1$-skeleton of the icosidodecahedron (rectified dodecahedron), i.e., the solid obtained by taking a regular dodecahedron and cutting off each corner with a plane that passes through the midpoints of the three edges meeting at that corner. $\endgroup$ – bof Dec 17 '14 at 19:36
  • $\begingroup$ @bof Thanks! I was wondering if it there was a name for this construction. Of course, it depends on how you identify the vertices; you could join the "same" vertices of degree 2 in both copies and obtain a graph with induced cycles of size 6, which is not isomorphic to the graph you mention. $\endgroup$ – David Hackenger Dec 17 '14 at 19:46
2
$\begingroup$

It seems the following.

You are right, this is an optimal bound as shows the following example. The set $B$ consists of 5 copies of the following hexagonal graph. To each monochromatic triangle corresponds a vertex from the set $A$, connected with the vertices of the triangle.

enter image description here

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.