Results 21 to 30 of about 3,049,614 (273)
An extremal problem on potentially K_p,1,1-graphic sequences [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 A sequence S is potentially K_p,1,1 graphical if it has a realization containing a K_p,1,1 as a subgraph, where K_p,1,1 is a complete 3-partite graph with partition sizes p,1,1.
Chunhui Lai
doaj +1 more source
Packing Tree Degree Sequences [PDF]
Graphs and Combinatorics, 2019 AbstractA degree sequence is a list of non-negative integers, $${D = d_1, d_2, \ldots , d_n}$$D=d1,d2,…,dn. It is called graphical if there exists a simple graph G such that the degree of the ith vertex is $$d_i$$di; G is then said to be a realization of D. A tree degree sequence is one that is realized by a tree.
Bérczi, Kristóf +3 more
openaire +8 more sources
Optimization over Degree Sequences [PDF]
SIAM Journal on Discrete Mathematics, 2018 We introduce and study the problem of optimizing arbitrary functions over degree sequences of hypergraphs and multihypergraphs. We show that over multihypergraphs the problem can be solved in polynomial time. For hypergraphs, we show that deciding if a given sequence is the degree sequence of a 3-hypergraph is NP-complete, thereby solving a 30 year ...
Deza, Antoine +3 more
openaire +2 more sources
A Degree Sequence Komlós Theorem [PDF]
SIAM Journal on Discrete Mathematics, 2019 20 pages, 4 figures. Author accepted manuscript.
Joseph Hyde, Hong Liu, Andrew Treglown
openaire +2 more sources
Spectral ordering and 2-switch transformations [PDF]
The American Journal of Combinatorics, 2022 We address the problem of ordering trees with the same degree sequence by their spectral radii. To achieve that, we consider 2-switch transformations which preserve the degree sequence and establish when the index decreases.
Elismar Oliveira +2 more
doaj +3 more sources
The irregularity of two types of trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 The irregularity of a graph $G$ is defined as the sum of weights $|d(u)-d(v)|$ of all edges $uv$ of $G$, where $d(u)$ and $d(v)$ are the degrees of the vertices $u$ and $v$ in $G$, respectively.
Li Jianxi, Yang Liu, Wai Shiu
doaj +1 more source
On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 Assume that $n, \delta ,k$ are integers with $0 \leq k < \delta < n$. Given a graph $G=(V,E)$ with $|V|=n$. The symbol $G-F, F \subseteq V$, denotes the graph with $V(G-F)=V-F$, and $E(G-F)$ obtained by $E$ after deleting the edges with at least one ...
Shih-Yan Chen, Shin-Shin Kao, Hsun Su
doaj +1 more source
The Random Plots Graph Generation Model for Studying Systems with Unknown Connection Structures
Entropy, 2022 We consider the problem of modeling complex systems where little or nothing is known about the structure of the connections between the elements. In particular, when such systems are to be modeled by graphs, it is unclear what vertex degree distributions
Evgeny Ivanko, Mikhail Chernoskutov
doaj +1 more source
On degree sequence optimization [PDF]
Operations Research Letters, 2020 We consider the problem of finding a subgraph of a given graph which maximizes a given function evaluated at its degree sequence. While the problem is intractable already for convex functions, we show that it can be solved in polynomial time for convex multi-criteria objectives.
openaire +3 more sources
Symmetric bipartite graphs and graphs with loops [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 Graph ...
Grant Cairns, Stacey Mendan
doaj +1 more source