A short constructive proof of the Erd?s-Gallai characterization of graphic lists

Erd?s and Gallai proved that a nonincreasing list (d₁,…,d_n) of nonnegative integers is the list of degrees of a graph (with no loops or multi-edges) if and only if the sum is even and the list satisfies for 1≤k≤n. We give a short constructive proof of the characterization.     

Collapsing unicolored graphs

A graph is said to be unicolored if it is colored by nonnegative integers so that adjacent points have colors that differ in absolute value by one. A unicolored graph is collapsible if it has a 1-factor that does not contain a 1-factor of any bicolored cycle. We show that a regular CW complex K cell collapses to a subcomplex O if and only if its relative unicolored incidence graph collapses. We consider the 1-factors and the bicolored cycles of unicolored incidence graphs and their relationship to the relative homology and homotopy properties of the pair of cell complexes.     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

Degree Conditions for k-Hamiltonian [a,b]-factors

Let a,b,k be nonnegative integers with 2≤a相似文献   

No-hole 2-distant colorings for Cayley graphs on finitely generated abelian groups

A no-hole 2-distant coloring of a graph Γ is an assignment c of nonnegative integers to the vertices of Γ such that |c(v)-c(w)|?2 for any two adjacent vertices v and w, and the integers used are consecutive. Whenever such a coloring exists, define nsp(Γ) to be the minimum difference (over all c) between the largest and smallest integers used. In this paper we study the no-hole 2-distant coloring problem for Cayley graphs over finitely generated abelian groups. We give sufficient conditions for the existence of no-hole 2-distant colorings of such graphs, and obtain upper bounds for the minimum span nsp(Γ) by using a group-theoretic approach.     

Nonnegatively realizable spectra with two positive eigenvalues

Boyle and Handelman [M. Boyle and D. Handelman, The spectra of nonnegative matrices via symbolic dynamics, Ann. Math. 133 (1991), pp. 249–316.] characterized all lists of n complex numbers that can be the nonzero spectrum of a nonnegative matrix. This article presents a constructive proof of this result in the special case when the lists are real and contain two positive numbers and n ? 2 negative numbers. A bound for the number of zeros that needs to be added to the list to achieve a nonnegative realization is presented in this case.     

House of Graphs: A database of interesting graphs

In this note we present House of Graphs (http://hog.grinvin.org) which is a new database of graphs. The key principle is to have a searchable database and offer–next to complete lists of some graph classes–also a list of special graphs that have already turned out to be interesting and relevant in the study of graph theoretic problems or as counterexamples to conjectures. This list can be extended by users of the database.     

Degree sets for digraphs

The degree setD _D of a digraphD is the set of outdegrees of the vertices ofD. For a finite, nonempty setS of nonnegative integers, it is shown that there exists an asymmetric digraph (oriented graph)D such thatD _D =S. Furthermore, the minimum order of such a digraphD is determined. Also, given two finite sequences of nonnegative integers, a necessary and sufficient condition is provided for which these sequences are the outdegree sequences of the two sets of an asymmetric bipartite digraph.     

Isolated Toughness and k-Hamiltonian [a,b]-factors

Acta Mathematicae Applicatae Sinica, English Series - Let a, b and k be nonnegative integers with a ≥ 2 and b ≥ a(k + 1) + 2. A graph G is called a k-Hamiltonian graph if after deleting...     

Notes on simplicial rook graphs

The simplicial rook graph \(\mathrm{SR}(m,n)\) is the graph of which the vertices are the sequences of nonnegative integers of length m summing to n, where two such sequences are adjacent when they differ in precisely two places. We show that \(\mathrm{SR}(m,n)\) has integral eigenvalues, and smallest eigenvalue \(s = \max \left( -n, -{m \atopwithdelims ()2}\right) \), and that this graph has a large part of its spectrum in common with the Johnson graph \(J(m+n-1,n)\). We determine the automorphism group and several other properties.     

图的分数κ-因子

给定图Ｇ＝（Ｖ,Ｅ）．设ａ和ｂ是两个非负整数．是一个函数．如果对所有的均成立,称 ｆ为 Ｇ的一个分数［ａ,ｂ］－ 因子． ａ＝ ｂ＝ κ时,称ｆ为 Ｇ的一个分数 ｋ＝因子．本文给出了一个图有分数 ｋ－因子的充分必要条件．     

The potential-Ramsey number of Kn and K t −k

Czechoslovak Mathematical Journal - A nonincreasing sequence π = (d1,…, dn) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices. In this...     

A New Lower Bound on the Potential-Ramsey Number of Two Graphs

A nonincreasing sequence π=(d₁,…,d_n) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.In this case,G is referred to as a realization of π.Given a graph H,a graphic sequence π is potentially H-graphic if π has a realization containing H as a subgraph.For graphs G₁ and G₂,the potential-Ramsey number r_pot(G₁,G₂) is the smallest integer k such that for every k-term graphic ...     

A simple criterion on degree sequences of graphs

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.     

[a,b]-因子包含给定圈的充分条件

设G是一个图且a,b是非负整数,a≤b.图G的一个[a,b]-因子是图G的一个支撑子图H且满足对所有的x∈V(G),a≤dH(x)≤b都成立.给出了图中[a,b]-因子包含给定圈的一个充分条件.     

A test for conjugacy of partitions of finite sets

In this note we present a simple test, involving a sequence of integers, which assures the conjugacy of a given partition P of a finite set S when our operations lead only to nonnegative integers. If negative integers appear in our operations, our test is inconclusive. The test, when conclusive, and an elementary property of permutations determine a conjugate for P.     

图的分数k-因子

给定图G=(V,E).设a和b是两个非负整数.fE→［0,1］是一个函数.如果     

A matching problem with side conditions

Given a graph G, a 2-matching is an assignment of nonnegative integers to the edges of G such that for each node i of G, the sum of the values on the edges incident with i is at most 2. A triangle-free 2-matching is a 2-matching such that no cycle of size 3 in G has the value 1 assigned to all of its edges. In this paper we describe explicity the convex hull of triangle-free 2-matchings by means of its extreme points and of its facets. We give a polynomially bounded algorithm which maximizes a linear function over the set of triangle-free 2-matchings. Finally we discuss some related problems.     

定向可图的度偶序列

n为非负整数序列，若存在以该序列为度序列的图，则称n为可图的，特别的，若此图是一个定向图，该序列则称为是定向可图的，本提出了一个判断序列是否为定向可图的充分必要条件，并且在定理的证明过程中给出了一个在定理条件下构造所求定向图的有效算法。     

Sum choice numbers of some graphs

Let f be a function assigning list sizes to the vertices of a graph G. The sum choice number of G is the minimum ∑_v∈V(G)f(v) such that for every assignment of lists to the vertices of G, with list sizes given by f, there exists proper coloring of G from the lists. We answer a few questions raised in a paper of Berliner, Bostelmann, Brualdi, and Deaett. Namely, we determine the sum choice number of the Petersen graph, the cartesian product of paths , and the complete bipartite graph K_3,n.