The Pseudoachromatic Number of a Graph

The pseudoachromatic number of a graph G is the maximum size of a vertex partition of G (where the sets of the partition may or may not be independent) such that, between any two distinct parts, there is at least one edge of G. This parameter is determined for graphs such as cycles, paths, wheels, certain complete multipartite graphs, and for other classes of graphs. Some open problems are raised.AMS Subject Classification (1991): primary 05C75 secondary 05C85     

关于亲和数的一个注记

本文研究了一类整数序列(2n)2n 1的某些性质,利用费玛数和数论函数的某些性质,获得了验证此类整数是否是亲和数和完全数的方法,既不与其他正整数构成亲和数对也不是完全数.     

Weak Hausdorff Gaps and the 𝔭 ≤ t Problem

We find topological characterizations of the pseudointersection number ?? and the tower number t of the real line and we show that ?? < t iff there exists a compact separable T₂ space X of π-weight < ?? that can be covered by < t nowhere dense sets iff there exists a weak Hausdorff gap of size K < t, i. e., a pair ({A : i ≠ k}, {B_J : j ε K}) C [W]^W X [U]W such that A = {A_i : i ε K} is a decreasing tower, B = {B_j : j ε K) is a family of pseudointersections of A, and there is no pseudointersection S of A meeting each member of B in an infinite set.     

Remarks on restrained domination and total restrained domination in graphs

The restrained domination number ^r(G) and the total restrained domination number _t ^r (G) of a graph G were introduced recently by various authors as certain variants of the domination number (G) of (G). A well-known numerical invariant of a graph is the domatic number d(G) which is in a certain way related (and may be called dual) to (G). The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.This research was supported by Grant MSM 245100303 of the Ministry of Education, Youth and Sports of the Czech Republic.     

关于调和数的一个结论

设n是大于1的正常数,并且设n=pα11p2α2…ptαt,其中pi为素数,i=1,2,…,t,ω(n)表示n的不同素因子的个数,即ω(n)=t.若n的所有因子的倒数和为整数,即0≤∑ij≤αjj=1,2,…,t1p1i1pi22…ptit为整数,称n是调和数.证明了和调和数相关的一个结论.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

On the relations of graph parameters and its total parameters

In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.     

Rainbow Numbers for Cycles with Pendant Edges

A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f (n, H) is the maximum number of colors in an edge-coloring of K _n with no rainbow copy of H. The rainbow number rb(n, H) is the minimum number of colors such that any edge-coloring of K _n with rb(n, H) number of colors contains a rainbow copy of H. Certainly rb(n, H) = f(n, H) + 1. Anti-Ramsey numbers were introduced by Erdős et al. [4] and studied in numerous papers. We show that for n ≥ k + 1, where C _k ⁺ denotes a cycle C _k with a pendant edge.     

On the Congruence σ(n)≡1(mod n)

Let k≥2 be an integer,and let σ(n) denote the sum of the positive divisors of an integer n.We call n a quasi-multiperfect number if σ(n)=kn+1.In this paper,we give some necessary properties of them.     

Friedman numbers have density 1

A Friedman number is a positive integer which is the result of an expression combining all of its own digits by use of the four basic operations, exponentiation and digit concatenation. One of the fundamental questions regarding Friedman numbers, first raised by Erich Friedman in August 2000, is how common they are among the integers. In this paper, we prove that Friedman numbers have density 1. We further prove that the density of Friedman numbers remains 1 regardless of the base of representation.     

On the b-chromatic number of Kneser graphs

In this note, we prove that for any integer n≥3 the b-chromatic number of the Kneser graph KG(m,n) is greater than or equal to . This gives an affirmative answer to a conjecture of [6].     

Upper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) =IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

Coloring graphs with crossings

We generalize the Five-Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K₆ as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings.     

Classroom note: A comparison of the method of least squares and the method of averages

Two techniques for determining a straight line fit to data are compared.     

ContributionsUpper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is calledΓ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) = IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

On the equality of the partial Grundy and upper ochromatic numbers of graphs

A (proper) k-coloring of a graph G is a partition Π={V₁,V₂,…,V_k} of V(G) into k independent sets, called color classes. In a k-coloring Π, a vertex v∈V_i is called a Grundy vertex if v is adjacent to at least one vertex in color class V_j, for every j, j<i. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. In this paper we introduce partial Grundy colorings, and relate them to parsimonious proper colorings introduced by Simmons in 1982.     

基于复数理论的同异型联系数及其应用

虽然联系数中的i与复数中的i有不同的含义,但所定义的同异型联系数与复数在形式上完全相同.为此,依据复数理论给出了同异型联系数的三角函数与指数函数两种表述形式及其互相转换,举例说明其应用,从而为发展联系数理论提供了新的途径.     

超图的某些参数间的关系

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows: DV(H) ≤DV(H) α(H) ≤ n; 2 ≤ DV (H) τ(H) ≤ n; 2 ≤ DV(H) v(H) ≤ n/2 [n/r]; DV (H) ρ(H) ≤n;2 ≤ De(H) DV(H) ≤ n/2 [n/r];α(H) De(H) ≤ n;2 ≤ De(H) v(H) ≤ 2[n/r];2 ≤De(H) ρ(H) ≤ n- r 2.     

黄金数的整数次幂与Fibonacci-Lucas数的若干关系式

给出Fibonacci等距子列定义,由此入手得到黄金数的整数次幂与Fibonacci数以及Lucas数的若干关系式.