New parameters involving chromatic sum in a graph

In this paper, we introduce four parameters which involve chromatic sum and independent domination. Corresponding to the chromatic sum coloring of G, the chromatic domination number, chromatic sum edge stability number, chromatic sum bondage number and domination chromatic sum color number are defined and studied.     

Tight bounds on the chromatic sum of a connected graph

The chromatic sum of a graph is introduced in the dissertation of Ewa Kubicka. It is the smallest possible total among all proper colorings of G using natural numbers. In this article we determine tight bounds on the chromatic sum of a connected graph with e edges.     

Lower bound of the sum of positive eigenvalues of a graph

1.IntroductionA(general)graphGisagraphwithloopsormultiedges,whileasimplegraphhasneitherloopsnormultiedges.ForagivengraphG,theedgesetandtheadjacencymatrixofGaredenotedbyE(G)andA(G)respectively.Moreover,weuseS(G),P(G)andq(G)todenotethesumofpositiveeigenvalues,thepositiveandnegativeinertiaindicesofA(G).In[l],C.DelormepointedoutthatS(G)5#E(G)withequalityohlyformatchings.Hefurtherputforwardthequestion:WhatisthelowerboundofS(G)foragiven#E(G)?Isit~?Inthispaperwegiveanaffirmativeanswertoth…     

图的彩虹连通数与最小度和

令G是一个阶为n且最小度为δ的连通图. 当δ很小而n很大时, 现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大, 它们是n的线性函数. 本文中, 我们用另一种参数,即k个独立点的最小度和σ_k来代替δ, 从而在很大程度上改进了彩虹边连通数和彩虹点连通数的上界. 本文证明了如果G有k个独立点, 那么rc(GG)≤3kn/(σk+k)+6k-3. 同时也证明了下面的结果, 如果σ_k≤7k或σ_k≥8k, 那么rvc(G)≤(4k+2k²)n/(σ_k+k)+5k; 如果7k<σ_k<8k, 那么rvc(G)≤(38k/9+2k²)n/(σ_k+k)+5k.文中也给出了例子说明我们的界比现有的界更好, 即我们的界为rc(G)≤9k-3和rvc(G)≤9k+2k²或rvc(G)≤83k/9+2k², 这意味着当δ很小而σ_k很大时, 我们的界是一个常数, 而现有的界却是n的线性函数.     

On the sum of all distances in a graph or digraph

The transmission of a graph or digraph G is the sum of all distances in G. Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2-connected or 2-edge-connected graphs of order n, the maximal transmission is realized only by the cycle C_n. The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP-hardness of some related algorithmic problems.     

On zero sum Ramsey numbers: Multiple copies of a graph

As a consequence of our main result, a theorem of Schrijver and Seymour that determines the zero sum Ramsey numbers for the family of all r-hypertrees on m edges and a theorem of Bialostocki and Dierker that determines the zero sum Ramsey numbers for r-hypermatchings are combined into a single theorem. Another consequence is the determination of zero sum Ramsey numbers of multiple copies of some small graphs.     

Computing the eccentric-distance sum for graph operations

In this paper, we present explicit formulas for computing the eccentric-distance sum of the most important graph operations such as the Cartesian product, join, composition, disjunction, symmetric difference, cluster and corona product of graphs. Also, we apply our results to compute this eccentricity-related invariant for some important classes of molecular graphs and nano-structures by specializing components of these graph operations.     

A sum labelling for the generalised friendship graph

We provide an optimal sum labelling scheme for the generalised friendship graph, also known as the flower (a symmetric collection of cycles meeting at a common vertex) and show that its sum number is 2.     

无和数列的倒数和

设A={a1,a2,...}是一个严格递增的正整数数列,如果每一个an都不能写成它前面一些不同项的和,则称A为无和数列.令ρ(A)=∑∞k=11ak.1962年,Erds证明了,对任意无和数列A,有ρ(A)103.1977年,Levine和O’Sullivan改进为ρ(A)3.9998.最近,Chen进一步改进为ρ(A)3.0752.本文证明了,对于无和数列A={a1,a2,...}(a1a2···),当a12时,有ρ(A)2.526.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

Sum and direct sum of frame sequences

Casazza, Han and Larson characterized various properties of the direct sum of two frame sequences. We add characterizations of other properties and study the relationship between the direct sum and the sum of frame sequences. In particular, we find a necessary and sufficient condition for the sum of two strongly disjoint (orthogonal) frame sequences (in the same Hilbert space) to be a frame sequence, and thereby show that the sum of two strongly disjoint frame sequences may not be a frame sequence. We also show that the closedness of the sum of the synthesis operators of two frame sequences and that of the sum of the frame operators of the same frame sequences are not related. Other observations are also included.     

A relationship between bounds on the sum of squares of degrees of a graph

LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex v_i ∈ V andm _i the average of the degrees of the vertices adjacent to vertexv _i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK _n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ .     

Spectral graph features for the classification of graphs and graph sequences

In this paper, the classification power of the eigenvalues of six graph-associated matrices is investigated. Each matrix contains a certain type of geometric/ spatial information, which may be important for the classification process. The performances of the different feature types is evaluated on two data sets: first a benchmark data set for optical character recognition, where the extracted eigenvalues were utilized as feature vectors for multi-class classification using support vector machines. Classification results are presented for all six feature types, as well as for classifier combinations at decision level. For the decision level combination, probabilistic output support vector machines have been applied, with a performance up to 92.4 %. To investigate the power of the spectra for time dependent tasks, too, a second data set was investigated, consisting of human activities in video streams. To model the time dependency, hidden Markov models were utilized and the classification rate reached 98.3 %.     

Bounds on the number of isolates in sum graph labeling

A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L(w)=L(u)+L(v). The sum number σ(G) of a graph G=(V,E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that σ(G)|E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G=(V,E) with fixed |V|3 and |E|, the average of σ(G) is at least

Full-size image

. In other words, for most graphs, σ(G)Ω(|E|).     

Signed graph factors and degree sequences

For a signed graph G and function , a signed f‐factor of G is a spanning subgraph F such that sdeg_F(υ) = f(υ) for every vertex υ of G, where sdeg(υ) is the number of positive edges incident with v less the number of negative edges incident with υ, with loops counting twice in either case. For a given vertex‐function f, we provide necessary and sufficient conditions for a signed graph G to have a signed f‐factor. As a consequence of this result, an Erd?s‐Gallai‐type result is given for a sequence of integers to be the degree sequence of a signed r‐graph, the graph with at most r positive and r negative edges between a given pair of distinct vertices. We discuss how the theory can be altered when mixed edges (i.e., edges with one positive and one negative end) are allowed, and how it applies to bidirected graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 27–36, 2006     

On Rauzy graph sequences of infinite words

Under study are the sequences of Rauzy graphs (i.e., the graphs of subwords overlapping) of infinite words. The k-stretching of a graph is the graph we obtain by replacing each edge with a chain of length k. Considering a sequence of strongly connected directed graphs of maximal in and out vertex degrees equal to s, we prove that it is, up to stretchings, a subsequence of a Rauzy graphs sequence of some uniformly recurrent infinite word on s-letter alphabet. The language of a word of this kind and stretching for a given sequence of graphs are constructed explicitly.