I am thinking of a quantitative (possibly based on random graph theory) or qualitative (say, based on topological ideas, e.g. Baire's theorem in the Gromov-Hausdorff metric space) information about how many finite graphs (perhaps: how many graphs on a given number of nodes $n$) are line graphs, or perhaps just generalized line graphs: these are those graphs whose adjacency matrix $A$ can be written as $A+2I=J^T J$, where $J^T J$ is the Gramian matrix of a vector system and $I$ is the identity (see the Godsil-Royle 2001 or Cvetkovic-Rowlinson-Simić 2004 for references).

Ideally, I would expect an assertion like: as $n\to \infty$, the probability of a graph on $n$ nodes to be a line graph goes to $0$. Or, even better: the probability goes to $1$ :)

  • 2
    $\begingroup$ Putting basic definitions into your question would help, otherwise you cut down your pool of potential answers by eliminating people who do not wish to go look up the references just to know what you mean by a line graph. $\endgroup$
    – Lee Mosher
    Dec 10 '16 at 15:48
  • 4
    $\begingroup$ Acttually, line graphs are basic knowledge in graph theory (I was assuming that if you don't know what's a line graph, you'd probably be unable to answer the question anyway). But I get your point and I have edited my question accordingly. $\endgroup$ Dec 10 '16 at 16:06
  • 3
    $\begingroup$ I don't know what any of the words mean, but I know how to use the internet to find that "Number of line graphs on $n$ unlabeled nodes" is tabulated at oeis.org/A132220 (and if you want labeled nodes, that's at oeis, too). $\endgroup$ Dec 10 '16 at 21:28

(Per request, post edited to discuss $G_{n,p}$ for values other than $p=1/2.$ This is a routine line of reasoning in probabilisitic combinatorics. See the first few chapters of Alon and Spencer for more.)

Line graphs are claw-free. And the random graph $G_{n, p}$ has in expectation $\Theta (n^4 p^3 (1-p)^3)$ claws (i.e., it's roughly some constant multiple of this). Having claws is not a monotone property, so we don't expect a classical threshold for when (as a function of $p$) we should think there ought to be claws. But nonetheless, a standard application of the second-moment method would tell you for what $p$ this property will hold almost surely (i.e., with probability tending to $1$ as $n$ tends to infinity). I did not check the following, but it's right up to some logs that I'm not writing:

The analysis splits into three regimes based on $p$.

  • If $n^{-4/3} \ll p \ll 1-n^{-4/3}$, then the number of claws will be concentrated about its mean, and the graph will have a claw with probability tending to $1$. Hence, the graph will fail to be a line graph almost surely.

  • If $p$ (resp $1-p$) is approximately of the form $C n^{-4/3}$, then the graph (or its complement) will be very sparse. I would guess that the number of claws would follow a Poison distribution, so it will be claw-free with probability tending to some $f(C)$. In this range, the graph (or its complement) will be extremely sparse, and in fact being claw-free would almost surely coincide with the property of being a disjoint union of paths (or its complement). Thus, in this range, $G_{n,p}$ (or its complement) will be a line graph with probability $f(C)$.

  • If $p \ll n^{-4/3}$ (resp. $1-p \ll n^{-4/3}$) then $G_{n, p}$ (resp. its complement) will almost surely be a disjoint union of paths, and hence it will be a line graph with probability tending to $1.$

[I'm being sloppy with the above treatment in the "critical window" when $p \approx n^{-4/3}.$ If you wanted to do this better, that's certainly possible.]

So in summary, unless $p$ is extremely small or extremely large, $G_{n,p}$ will almost surely fail to be a line graph. In particular, this holds for $p=1/2$, so almost all graphs fail to be line graphs.

  • $\begingroup$ Thanks! But I do not know or understand your notation. Could you give me a reference for your assertion? And by the way, how does the picture change if you consider $G_{n,p}$ for $p\ne \frac{1}{2}$? $\endgroup$ Dec 13 '16 at 9:04
  • $\begingroup$ I'll add a few links. The theta-notation is Landau notation. (See en.m.wikipedia.org/wiki/Big_O_notation ) $\endgroup$
    – Pat Devlin
    Dec 13 '16 at 9:30
  • $\begingroup$ Links added, and I also (considerably!) expanded the post to include a discussion of $G_{n,p}$ for general $p.$ $\endgroup$
    – Pat Devlin
    Dec 13 '16 at 10:22

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.