共查询到20条相似文献,搜索用时 15 毫秒
1.
A sequence {d
1, d
2, . . . , d
n
} of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v
1, v
2, . . . , v
n
such that the degree d(v
i
) of the vertex v
i
equals d
i
for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize
sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl
Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler,
Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow. 相似文献
2.
A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler’s inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from and . 相似文献
3.
Amitabha Tripathi 《Discrete Applied Mathematics》2008,156(18):3513-3517
A finite sequence of nonnegative integers is called graphic if the terms in the sequence can be realized as the degrees of vertices of a finite simple graph. We present two new characterizations of graphic sequences. The first of these is similar to a result of Havel-Hakimi, and the second equivalent to a result of Erd?s & Gallai, thus providing a short proof of the latter result. We also show how some known results concerning degree sets and degree sequences follow from our results. 相似文献
4.
《Discrete Mathematics》2019,342(6):1687-1695
We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree degree sequences, we obtain closed formulas for the possible values. For bipartite degree sequences, we show the existence of realizations with a restricted structure, which allows to derive an analogue of the Gale–Ryser Theorem characterizing bipartite degree sequences. More precisely, we show that a bipartite degree sequence has a realization with a certain matching number if and only if a cubic number of inequalities similar to those in the Gale–Ryser Theorem are satisfied. For tree degree sequences as well as for bipartite degree sequences, the possible values of the matching number form intervals. 相似文献
5.
Peter J. Cameron 《Designs, Codes and Cryptography》1996,8(3):109-133
The main theme of this article is that counting orbits of an infinite permutation group on finite subsets or tuples is very closely related to combinatorial enumeration; this point of view ties together various disparate stories. Among these are reconstruction problems, the relation between connected and arbitrary graphs, the enumeration of N-free posets, and some of the combinatorics of Stirling numbers.Dedicated to Hanfried Lenz on the occasion of his 80th birthday. 相似文献
6.
Two graphs are said to be -cospectral (respectively, -cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph is said to be (respectively, ) if there does not exist other non-isomorphic graph such that and are -cospectral (respectively, -cospectral). Let be the degree sequence of a graph with vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with ), if is -cospectral (respectively, -cospectral) with a connected graph and , then has the same degree sequence as . A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both , which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014). 相似文献
7.
Xiao-Dong Zhang 《Discrete Applied Mathematics》2009,157(13):2928-2937
In this paper, we investigate the properties of the largest signless Laplacian spectral radius in the set of all simple connected graphs with a given degree sequence. These results are used to characterize the unicyclic graphs that have the largest signless Laplacian spectral radius for a given unicyclic graphic degree sequence. Moreover, all extremal unicyclic graphs having the largest signless Laplacian spectral radius are obtained in the sets of all unicyclic graphs of order n with a specified number of leaves or maximum degree or independence number or matching number. 相似文献
8.
Regina Tyshkevich 《Discrete Mathematics》2000,220(1-3):201-238
9.
Let G be a graph of order n and k a positive integer. A set of subgraphs H={H1,H2,…,Hk} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H1,…,Hk are vertex disjoint subgraphs of G such that and for all i, 1≤i≤k, Hi is a cycle or K1 or K2. If, in addition, for all i, 1≤i≤k, Hi is a cycle or K1, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G has a k-DCP, except G≅C5 and k=2. We prove that if G is a graph of order n≥k+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K2∪Kn−2∪{e}, where e is an edge connecting V(K2) and V(Kn−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}. 相似文献
10.
In this paper, we characterize all extremal connected bicyclic graphs with the largest signless Laplacian spectral radius in the set of all connected bicyclic graphs with prescribed degree sequences. Moreover, the signless Laplacian majorization theorem is proved to be true for connected bicyclic graphs. As corollaries, all extremal connected bicyclic graphs having the largest signless Laplacian spectral radius are obtained in the set of all connected bicyclic graphs of order n (resp. all connected bicyclic graphs with a specified number of pendant vertices, and all connected bicyclic graphs with given maximum degree). 相似文献
11.
Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(kCℓ,n) such that each n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(kCℓ,n) has a realization G containing a cycle of length r for each r, krℓ. 相似文献
12.
Let r≥ 1, k≥ 2 and Fm1 ,...,mki;r denote the most general definition of a friendship graph, that is, the graph of Kr+m1 , . . . , Kr+mk meeting in a common r set, where Kr+mi is the complete graph on r + mi vertices. Clearly, | Fm1 ,...,mki;r | = m1+ ··· + mk + r. Let σ(Fm1 ,...,mki;r , n) be the smallest even integer such that every n-term graphic sequence π = (d1, d2, . . . , dn) with term sum σ(π) = d1 + d2 + ··· + dn ≥σ(Fm1 ,...,mki;r,n) has a realization G containing Fm1 ,...,mki;r as a subgraph. In this paper, we determine σ(Fm1 ,...,mki;r,n) for n sufficiently large. 相似文献
13.
14.
Alexandru Ioan Tomescu 《Discrete Applied Mathematics》2008,156(1):125-130
In this paper characterizations of connected unicyclic and bicyclic graphs in terms of the degree sequence, as well as the graphs in these classes minimal with respect to the degree distance are given. 相似文献
15.
Let Dn(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope Dn(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes Dn(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on Dn(2). Our main results concern the extreme points and facets of Dn(r). We characterize adjacency of extreme points of Dn(r) and, in the case r=2, determine the distance between two given vertices in the graph of Dn(2). We give a characterization of when a linear inequality determines a facet of Dn(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of Dn(2); find an explicit family of Erdös–Gallai type facets of Dn(r); and describe a simple lifting procedure that produces a facet of Dn+1(r) from one of Dn(r). 相似文献
16.
In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows: let
G(n; {p
k
}) be the probability space of all the labelled loopless multigraphs with vertex set V = {υ
1, υ
2, …, υ
n
}, in which the distribution of tvi ,vj t_{v_i ,v_j } , the number of the edges between any two vertices υ
i
and υ
j
is
P{ tvi ,vj = k} = pk ,k = 0,1,2,...P\{ t_{v_i ,v_j } = k\} = p_k ,k = 0,1,2,... 相似文献
17.
As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope Pn. In this paper, we show that Pn is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of Pn, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153]. 相似文献
18.
19.
This paper considers a degree sum condition sufficient to imply the existence of vertex-disjoint cycles in a graph . For an integer , let be the smallest sum of degrees of independent vertices of . We prove that if has order at least and , with , then contains vertex-disjoint cycles. We also show that the degree sum condition on is sharp and conjecture a degree sum condition on sufficient to imply contains vertex-disjoint cycles for . 相似文献
20.
The neighborhood degree list (NDL) is a graph invariant that refines information given by the degree sequence and joint degree matrix of a graph and is useful in distinguishing graphs having the same degree sequence. We show that the space of realizations of an NDL is connected via a switching operation. We then determine the NDLs that have a unique realization by a labeled graph; the characterization ties these NDLs and their realizations to the threshold graphs and difference graphs. 相似文献
|