TAILIEUCHUNG - Báo cáo toán học: "On the functions with values in [α(G), χ(G)]"

Let G be a graph with vertex set V (G) = {1, . . . , n} and edge set E(G). We are interested in studying the functions of the graph G whose values belong to the interval [ (G), (G)]. Here (G) is the size of the largest stable set in G and (G) is the smallest number of cliques that cover the vertices of G. It is well known (see, for example, [1]) that for some 0 it is impossible to approximate in polynomial time (G) and (G) within a factor of n , assuming P 6= NP. We suppose that better approximation could. | On the functions with values in G x G V. Dobrynin M. Pliskin and E. Prosolupov St. Petersburg State University St. Petersburg Russia vdobr pev @ Submitted Nov 25 2003 Accepted Mar 15 2004 Published Mar 22 2004 MR Subject Classification 05C50 Abstract Let B G X X E Rnxn X XT I X I A G and C G X X E Rnxn X XT I - A G X I A G be classes of matrices associated with graph G. Here n is the number of vertices in graph G and A G is the adjacency matrix of this graph. Denote r G minXeC G rank X r G minXeg G rank X . We have shown previously that for every graph G a G r G x G holds and a G r G implies a G x G . In this article we show that there is a graph G such that a G r G but a G x G . In the case when the graph G doesn t contain two chordless cycles C4 with a common edge the equality a G r G implies a G x G . Corollary the last statement holds for d G - the minimal dimension of the orthonormal representation of the graph G. Let G be a graph with vertex set V G 1 . n and edge set E G . We are interested in studying the functions of the graph G whose values belong to the interval n G x G . Here n G is the size of the largest stable set in G and x G is the smallest number of cliques that cover the vertices of G. It is well known see for example 1 that for some e 0 it is impossible to approximate in polynomial time n G and x G within a factor of ne assuming P NP. We suppose that better approximation could be obtained for narrow classes of graphs determined on the basis of a system of functions of graph G sandwiched between a G and x G . One such function is the well known Lovasz function 0 G 7 which has many alternative definitions. One of them is based on the notion of the orthonormal labeling of the graph. Orthonormal labeling of dimension k of the graph G is a mapping f V G Rfc such that f v 2 1 for all v E V G and f vị f vj 0 if vị Vj e E G . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N5 1 Let ei E Rfc be a unit vector which is 0 in all .

• Báo cáo khoa học
• On the functions
• values in [α(G
• reports of mathematics
• mathematical works
• Even circuits
• prescribed clockwise parity
• scientific reports
• scientific research
• Some Functions known
• High School
• hyperbolic functions
• Inverse functions
• general
• Arcus Functions
• Area functions
• theoretical results
• Polynomials
• Fractional functions
• exponential function
• Trigonometric
• Harmonic functions
• logarithm function
• Handbook of mathematical functions
• Mathematical tables
• Coulomb wave functions
• Hypergeometric functions
• Weierstrass elliptic
• Mathieu functions
• Parabolic cylinder functions
• Analytic functions
• Univalent functions
• Bi univalent functions
• Subordination between analytic functions
• Hankel determinant
• Lecture Mathematics
• Graphing circular functions
• Graphing sine functions
• Graphing cosine functions
• Graphs of the tangent
• Trigonometric functions of angles
• Predefined Functions
• Using Predefined Functions
• The Function Call
• More Predefined Functions
• Predefined Void Functions
• Programmer Defined Functions
• Physical constants
• Elementary analytical methods
• Elementary transcendental functions
• Exponential integral
• Related functions
• Legendre functions
• Varieties and levels of nitrogen
• Levels of nitrogen on growth functions
• Nitrogen on growth functions
• Growth functions of wheat
• Growth functions
• Lecture Business mathematics
• Bài giảng Toán kinh doanh
• Business mathematics
• Non linear functions
• Polynomial functions
• Exponential functions
• Logarithmic functions
• Point Sets
• Examinations of functions
• Level curves
• level surfaces
• Conics
• Continuous functions
• Description of curves
• Connected sets
• Doctor of Philosophy in Mathematics
• Linear and Non linear Operators
• The Distribution of Zeros of Entire Functions
• Polynomials and transcendental entire functions
• Linear operators acting on entire functions
• Multiplier sequences with various polynomial bases
• Chapter 1 vector functions
• Vector functions and space curves
• Derivatives and integrals of vector functions
• Arc length and curvature
• Motion in space
• Lecture Charter 5 C Functions
• Lecture C Functions
• Program Modules in C
• Math library functions
• Function definitions
• Function call stack
• Activation records
• P valent
• P valently colse to convex functions
• P valently starlike functions
• P valently convex functions
• Open unit disk
• Geometric function
• Subordination principle
• Carathedory functions
• Janowski Starlike functions
• Starlike functions of order β
• The radius of Starlikeness
• The complete reference
• The standard template library
• The mathematical functions
• The string and character functions
• The dynamic allocation functions
• Localization functions
• Exception handling
• ICT 5 Web Development
• Functions Basic PHP Functions
• Write your own functions
• Using External Script Files
• The abs Functionabs
• The sqrt Function
• Bi close to convex functions
• Faber polynomials
• Coefficient estimates
• Rule of Four
• Functions and change
• Trigonometric functions
• The Derivative
• Short cuts to differentiation
• Functions os several variables
• A fundamental tool
• Differentiating functions of several variables
• Calculus early transcendental functions
• Transcendental functions
• Parametric equations
• Polar coordinates
• Vector valued functions
• Several variables
• Operations on functions
• Composition of functions
• Applications of functions
• Graphs of equations
• Slope of a line
• Real exponents
• Exponential expressions
• Vibrant search mechanism for numerical optimization functions
• Vibrant search mechanism
• Numerical optimization functions
• Non shifted optimization functions
• The overall search performance of HSA