Name
Abstract | ||
|---|---|---|
We calculate genus distribution formulas for several families of ring-like graphs and prove that they are log-concave. The graphs in each of our ring-like families are obtained by applying the self-bar-amalgamation operation to the graphs in a linear family (linear in the sense of Stahl). That is, we join the two root-vertices of each graph in the linear family. Although log-concavity has been proved for many linear families of graphs, the only other ring-like sequence of graphs of rising maximum genus known to have log-concave genus distributions is the recently reinvestigated sequence of Ringel ladders. These new log-concavity results are further experimental evidence in support of the long-standing conjecture that the genus distribution of every graph is log-concave. Further evidence in support of the general conjecture is the proof herein that each partial genus distribution, relative to face-boundary walk incidence on root vertices, of an iterative bar-amalgamations of copies of various given graphs is log-concave, which is an unprecedented result for partitioned genus distributions. Our results are achieved via introduction of the concept of a vectorized production matrix, which seems likely to prove a highly useful operator in the theory of genus distributions and via a new general result on log-concavity. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ejc.2014.05.008 | European Journal of Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Modular decomposition,Indifference graph,Lévy family of graphs,Clique-sum,Chordal graph,Genus (mathematics),Pathwidth,1-planar graph,Mathematics | Journal | 42 |
ISSN | Citations | PageRank |
0195-6698 | 2 | 0.38 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jonathan L. Gross | 1 | 458 | 268.73 |
| Toufik Mansour | 2 | 423 | 87.76 |
| Thomas W. Tucker | 3 | 191 | 130.07 |