Return to Question

Is there a more interesting name for this graph invariant? It seems to have been called 'complexity' in

• Remco van der Hofstad, Joel Spencer, Counting Connected Graphs Asymptotically, European Journal of Combinatorics 27 Issue 8 (2006) 1294–1320, doi:10.1016/j.ejc.2006.05.006, arXiv:math/0502579

and in

• Joel Spencer, Probabilistic Methods in Combinatorics In: Chatterji S.D. (eds) Proceedings of the International Congress of Mathematicians, Birkhäuser, Basel (1995), doi:10.1007/978-3-0348-9078-6_132, Wayback Machine pdf of article, big IMU pdf of whole volume

The motivation is that we want to talk about a quantity that is preserved under the graph transformation of collapsing two distinct vertices connected by an edge to a single vertex (thereby removing one edge and one vertex, preserving 'edges minus vertices'). So for example if the quantity 'edges minus vertices plus one' is more natural for some reason and has a name, then this would also be helpful. The concept should not be restricted to e.g. planar graphs.

Is there a more interesting name for this graph invariant: edges minus vertices? It seems to have been called 'complexity' in

• Remco van der Hofstad, Joel Spencer, Counting Connected Graphs Asymptotically, European Journal of Combinatorics 27 Issue 8 (2006) 1294–1320, doi:10.1016/j.ejc.2006.05.006, arXiv:math/0502579

and in

• Joel Spencer, Probabilistic Methods in Combinatorics In: Chatterji S.D. (eds) Proceedings of the International Congress of Mathematicians, Birkhäuser, Basel (1995), doi:10.1007/978-3-0348-9078-6_132, Wayback Machine pdf of article, big IMU pdf of whole volume

The motivation is that we want to talk about a quantity that is preserved under the graph transformation of collapsing two distinct vertices connected by an edge to a single vertex (thereby removing one edge and one vertex, preserving 'edges minus vertices'). So for example if the quantity 'edges minus vertices plus one' is more natural for some reason and has a name, then this would also be helpful. The concept should not be restricted to e.g. planar graphs.

Is there a more interesting name for this graph invariant? It seems to have been called 'complexity' here http://arxiv.org/abs/math/0502579 and here http://www.mathunion.org/ICM/ICM1994.2/Main/icm1994.2.1375.1383.ocr.pdf .

The motivation is that we want to talk about a quantity that is preserved under the graph transformation of collapsing two distinct vertices connected by an edge to a single vertex (thereby removing one edge and one vertex, preserving 'edges minus vertices'). So for example if the quantity 'edges minus vertices plus one' is more natural for some reason and has a name, then this would also be helpful. The concept should not be restricted to e.g. planar graphs.

Is there a more interesting name for this graph invariant? It seems to have been called 'complexity' in

• Remco van der Hofstad, Joel Spencer, Counting Connected Graphs Asymptotically, European Journal of Combinatorics 27 Issue 8 (2006) 1294–1320, doi:10.1016/j.ejc.2006.05.006, arXiv:math/0502579

and in

• Joel Spencer, Probabilistic Methods in Combinatorics In: Chatterji S.D. (eds) Proceedings of the International Congress of Mathematicians, Birkhäuser, Basel (1995), doi:10.1007/978-3-0348-9078-6_132, Wayback Machine pdf of article, big IMU pdf of whole volume

The motivation is that we want to talk about a quantity that is preserved under the graph transformation of collapsing two distinct vertices connected by an edge to a single vertex (thereby removing one edge and one vertex, preserving 'edges minus vertices'). So for example if the quantity 'edges minus vertices plus one' is more natural for some reason and has a name, then this would also be helpful. The concept should not be restricted to e.g. planar graphs.

Is there a more interesting name for this graph invariant? It seems to have been called 'complexity' here http://arxiv.org/abs/math/0502579 and here http://www.mathunion.org/ICM/ICM1994.2/Main/icm1994.2.1375.1383.ocr.pdf .

The motivation is that we want to talk about a quantity that is preserved under the graph transformation of collapsing two vertices connected by an edge to a single vertex (thereby removing one edge and one vertex, preserving 'edges minus vertices'). So for example if the quantity 'edges minus vertices plus one' is more natural for some reason and has a name, then this would also be helpful. The concept should not be restricted to e.g. planar graphs.

Is there a more interesting name for this graph invariant? It seems to have been called 'complexity' here http://arxiv.org/abs/math/0502579 and here http://www.mathunion.org/ICM/ICM1994.2/Main/icm1994.2.1375.1383.ocr.pdf .

The motivation is that we want to talk about a quantity that is preserved under the graph transformation of collapsing two distinct vertices connected by an edge to a single vertex (thereby removing one edge and one vertex, preserving 'edges minus vertices'). So for example if the quantity 'edges minus vertices plus one' is more natural for some reason and has a name, then this would also be helpful. The concept should not be restricted to e.g. planar graphs.