Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelf-dual polyhedra of given degree sequence
62
0
0.0
(
0
)
Authors
Riccardo W. Maffucci
Ask ChatGPT about the research
No Arabic abstract
Given vertex valencies admissible for a self-dual polyhedral graph, we describe an algorithm to explicitly construct such a polyhedron. Inputting in the algorithm permutations of the degree sequence can give rise to non-isomorphic graphs. As an application, we find as a function of $ngeq 3$ the minimal number of vertices for a self-dual polyhedron with at least one vertex of degree $i$ for each $3leq ileq n$, and construct such polyhedra. Moreover, we find a construction for non-self-dual polyhedral graphs of minimal order with at least one vertex of degree $i$ and at least one $i$-gonal face for each $3leq ileq n$.
rate research
Read More
We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$, when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.
For a labeled tree on the vertex set $set{1,2,ldots,n}$, the local direction of each edge $(i,j)$ is from $i$ to $j$ if $i<j$. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence $lambda = 1^{e_1}2^{e_2} ldots$ of a tree on the vertex set $set{1,2,ldots,n}$ is a partition of $n-1$. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prufer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a $q$-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.
The greedy tree $mathcal{G}(D)$ and the $mathcal{M}$-tree $mathcal{M}(D)$ are known to be extremal among trees with degree sequence $D$ with respect to various graph invariants. This paper provides a general theorem that covers a large family of invariants for which $mathcal{G}(D)$ or $mathcal{M}(D)$ is extremal. Many known results, for example on the Wiener index, the number of subtrees, the number of independent subsets and the number of matchings follow as corollaries, as do some new results on invariants such as the number of rooted spanning forests, the incidence energy and the solvability. We also extend our results on trees with fixed degree sequence $D$ to the set of trees whose degree sequence is majorised by a given sequence $D$, which also has a number of applications.
The Steiner distance of vertices in a set $S$ is the minimum size of a connected subgraph that contain these vertices. The sum of the Steiner distances over all sets $S$ of cardinality $k$ is called the Steiner $k$-Wiener index and studied as the natural generalization of the famous Wiener index in chemical graph theory. In this paper we study the extremal structures, among trees with a given segment sequence, that maximize or minimize the Steiner $k$-Wiener index. The same extremal problems are also considered for trees with a given number of segments.
Let $G$ be a simple graph with $ngeq4$ vertices and $d(x)+d(y)geq n+k$ for each edge $xyin E(G)$. In this work we prove that $G$ either contains a spanning closed trail containing any given edge set $X$ if $|X|leq k$, or $G$ is a well characterized graph. As a corollary, we show that line graphs of such graphs are $k$-hamiltonian.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
