I am interested in graphs $G=(V,E)$ with vertex set $V$ a finite dimensional vector space and edges in $E$ which are not necessarily related to the linear structure of $V$. So my objects are just graphs with a vertex set with additional structure, and I don't require any special morphisms. (The vector space structure is for combinatorial reasons, to count vertices in terms of dimension.) I'd like to use a striking name for those graphs, but neither do I know if

1) there is already a name for them,

2) there would be collision with other terminology if I named them something like "vector graphs", "vector based graphs", etc.

For example "linear graph" would be a bad choice.

If some graph theory terminology specialist out there could help that would be very nice.


Your set-up sounds reminiscent of work in algebraic combinatorics where people associate vector spaces to the rank levels of a graded poset (whose Hasse diagram is of course a graph) to help establish unimodality of the rank-generating function. I'm not sure whether a special name is given to this extra vector space structure (except in the very nice case when these vector spaces turn out to be the weight spaces in a Lie algebra). But you might find it interesting/useful to take a look e.g. at the following survey paper on this topic:

Richard Stanley, Some applications of algebra to combinatorics, Discrete Applied Math. 34 (1991), 241--277.

  • $\begingroup$ @Abel: my answer is mostly related to your parenthetical remark, which led me to believe you wanted a comma after "finite vertex set $V$" in the first line of your question -- which changes the meaning of the question a lot, I think. Anyway, my answer is based on that reading of your question. $\endgroup$ – Patricia Hersh Sep 15 '12 at 13:13

Your situation reminds me of vertex colored graphs, that is graphs whose vertices are colored such that no two vertices of the same color share an edge. (See for example here: http://en.wikipedia.org/wiki/Graph_coloring ) You could then just use the dimension of the vector space associated to a vertex as its color. But it's not clear to me whether you objects satisfy this additional assumption on adjacency.

  • $\begingroup$ No, they don't. In fact there are colors involved, but they are fairly independent of the dimension. $\endgroup$ – Abel Stolz Sep 18 '12 at 8:19
  • $\begingroup$ well, then sorry for the not really helpful remark. $\endgroup$ – Petra Schwer Sep 19 '12 at 8:02

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.