ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let FF and GG be graphs. The FF-degree of a vertex vv in GG is the number of subgraphs of GG isomorphic to FF that contain vv. A graph GG is FF-irregular if any two distinct vertices of GG have different FF-degrees.

Existence conjecture. For every connected graph FF on three or more vertices, there exists an FF-irregular graph.

The conjecture generalizes the known existence results for complete graphs and stars. It was later strengthened by the assertion that infinitely many such graphs exist for every connected graph FF of order at least 33; the general conjecture is solved here only for the class of graphs FF of diameter 22.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.