On the power sequence of a graph

Necessary and sufficient conditions for a sequence (p ₁,p ₂, …,p _n ) of positive integers to be the power sequence of a connected graph onn vertices withm edges are given. The maximum power of a connected graph onn vertices withm edges and the class of all extremal graphs are also determined.     

On Cycle Sequences

. For each vertex v in a graph G, the maximum length of a cycle which passes through v is called the cycle number of v, denoted by c(v). A sequence a ₁,a ₂,…,a _n of nonnegative integers is called a cycle sequence of a graph G if the vertices of G can be labeled as v ₁,v ₂,…,v _n such that a _i =c(v _i ) for 1≤i≤n. We give some sufficient and necessary conditions for a sequence to be a cycle sequence. We can thereby derive a polynomial time procedure for recognizing cycle sequences. Received: July 14, 1997 Final version received: June 15, 1998     

Some Algebraic Methods for Calculating the Number of Colorings of a Graph

With an arbitrary graph G having n vertices and m edges, and with an arbitrary natural number p, we associate in a natural way a polynomial R(x ₁,...,x _n) with integer coefficients such that the number of colorings of the vertices of the graph G in p colors is equal to p ^m-n R(0,...,0). Also with an arbitrary maximal planar graph G, we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph G in 3 colors can be calculated in several ways via the coefficients of each of these polynomials. Bibliography: 2 titles.     

Minimum degree conditions for -linked graphs

For a fixed multigraph H with vertices w₁,…,w_m, a graph G is H-linked if for every choice of vertices v₁,…,v_m in G, there exists a subdivision of H in G such that v_i is the branch vertex representing w_i (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and n7.5k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D(H,n) appears to equal the least integer d^′ such that every n-vertex graph with minimum degree at least d^′ is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H.     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪I _p). Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).     

Sphere and Dot Product Representations of Graphs

A graph G is a k-sphere graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the distance between v _i and v _j is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the dot product of v _i and v _j is at least 1.     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.     

n-Tuple Coloring of Planar Graphs with Large Odd Girth

 The main result of the papzer is that any planar graph with odd girth at least 10k−7 has a homomorphism to the Kneser graph G _k ^{2 k +1}, i.e. each vertex can be colored with k colors from the set {1,2,…,2k+1} so that adjacent vertices have no colors in common. Thus, for example, if the odd girth of a planar graph is at least 13, then the graph has a homomorphism to G ₂ ⁵, also known as the Petersen graph. Other similar results for planar graphs are also obtained with better bounds and additional restrictions. Received: June 14, 1999 Final version received: July 5, 2000     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

Orientations of circle graphs

Let C(v₁, …,v_n) be a system consisting of a circle C with chords v₁, …,v_n on it having different endpoints. Define a graph G having vertex set V(G) = {v₁, …,v_n} and for which vertices v_i and v_j are adjacent in G if the chords v_i and v_j intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v₁, …,v_n) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v₁, …,v_n) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

The degree distribution of the random multigraphs

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 = {υ ₁, υ ₂, …, υ _n }, in which the distribution of t_{vi ,vj} t_{v_i ,v_j } , the number of the edges between any two vertices υ _i and υ _j is

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Graph decompositions without isolated vertices III

Let G be a graph of order n, and n = Σ^k_i=1 a_i be a partition of n with a_i ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v₁,…, v_k of G, the vertex set V(G) can be decomposed into k disjoint subsets A₁,…, A_k so that |A_i| = a_i,v_iisA_i is an element of A_i and “the subgraph induced by A_i contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

OD-characterization of Almost Simple Groups Related to U3（5）

Let G be a finite group with order ｜G｜=p1^α1p2^α2……pk^αk, where p1 〈 p2 〈……〈 Pk are prime numbers. One of the well-known simple graphs associated with G is the prime graph （or Gruenberg- Kegel graph） denoted .by г（G） （or GK（G））. This graph is constructed as follows： The vertex set of it is π（G） = {p1,p2,…,pk} and two vertices pi, pj with i≠j are adjacent by an edge （and we write pi - pj） if and only if G contains an element of order pipj. The degree deg（pi） of a vertex pj ∈π（G） is the number of edges incident on pi. We define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, which is called the degree pattern of G. A group G is called k-fold OD-characterizable if there exist exactly k non- isomorphic groups H such that ｜H｜ = ｜G｜ and D（H） = D（G）. Moreover, a 1-fold OD-characterizable group is simply called OD-characterizable. Let L ：= U3（5） be the projective special unitary group. In this paper, we classify groups with the same order and degree pattern as an almost simple group related to L. In fact, we obtain that L and L.2 are OD-characterizable; L.3 is 3-fold OD-characterizable; L.S3 is 6-fold OD-characterizable.     

Potentially <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> — <Emphasis Type="Italic">G</Emphasis>-graphical sequences: A survey

The set of all non-increasing nonnegative integer sequences π = (d(v ₁), d(v ₂), …, d(v _n )) is denoted by NS _n . A sequence π ∈ NS _n is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of π. The set of all graphic sequences in NS _n is denoted by GS _n . A graphical sequence π is potentially H-graphical if there is a realization of π containing H as a subgraph, while π is forcibly H-graphical if every realization of π contains H as a subgraph. Let K _k denote a complete graph on k vertices. Let K _m −H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of K _m ). This paper summarizes briefly some recent results on potentially K _m −G-graphic sequences and give a useful classification for determining σ (H, n).     

Degree series of the 3-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant λ such that the equality λd（vi） = Σ（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,..., ｜V（G）｜, where d（vi） denotes the degree of vertex vi. Let ni denote the number of vertices with degree i. This paper deals with the 3-Hgraphs and determines their degree series. Moreover, the 3-Hgraphs with bounded ni （1 ≤ i ≤ 7） are studied and some interesting results are obtained.     

Hamiltonian Cycles in Almost Claw-Free Graphs

 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G ₁, G ₂ and G ₃ such that E _G (G _i , G _j ) = {u _i , u _j , v _i v _j } for i≠j and i,j = 1, 2, 3 (where u _i ≠v _i ∈V(G _i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999