Let $f(G)$ denote any parameter of a graph $G$ for which $f(G) \geq f(G - \{v \})$, where $v$ is any vertex in $G$. We could describe such parameters as being monotone under vertex deletion. Does anyone know where I could find a reasonably comprehensive list of such parameters? If so, thank you.
5
-
1$\begingroup$ These seems to be rather general and vague. For instance, any monotonic function of the number of vertices furnishes one such class; I guess you are searching for some "interesting" members of this class...perhaps you are interested in something more specific? $\endgroup$– SuvritCommented Oct 13, 2013 at 18:49
-
1$\begingroup$ Let $f(G)$ be a graph parameter and define $F(G)$ to be the maximum value of $f(H)$ over all induced subgraphs of $G$. Then $F(G)$ is monotone. So there does seem to be an oversupply of examples. $\endgroup$– Chris GodsilCommented Oct 13, 2013 at 20:13
-
2$\begingroup$ Function $f$ has the required nature iff the properties $f(G)\le k$ are hereditary for each $k$. There is a fairly large literature dealing with hereditary properties (but alas not every author defines it the same way). No chance of a list, as suv..rit and Chris wrote. $\endgroup$– Brendan McKayCommented Oct 14, 2013 at 1:57
-
$\begingroup$ Thank you for these comments. Just to be clear, my question is referring to graph parameters (such as the spectral radius or maximum degree which satisfy this monotone criteria) and not to graph properties (such as planar or complete). Perhaps someone has done a Masters thesis or similar on such parameters? Clive Elphick $\endgroup$– clive elphickCommented Oct 14, 2013 at 7:48
-
$\begingroup$ @Sergiy: please be careful when adding MathJax/TeX; the post now had missing braces as they were not escaped after adding the dollars. $\endgroup$– user9072Commented Oct 14, 2013 at 12:28
Add a comment
|