Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The excessive [3]-index of all graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The excessive [3]-index of all graphs. | The excessive 3 -index of all graphs David Cariolaro Department of Mathematical Sciences Xi an Jiaotong-Liverpool University Suzhou Jiangsu China 215123 davidcariolaro@hotmail.com Hung-Lin Fu Department of Applied Mathematics National Chiao Tung University Hsin Chu Taiwan 30050 hlfu@math.nctu.edu.tw Submitted May 14 2008 Accepted Sep 25 2009 Published Oct 5 2009 Mathematics Subject Classification 05C15 05C70 Abstract Let m be a positive integer and let G be a graph. A set M of matchings of G all of which of size m is called an m -covering of G if uMeM M E G . G is called m -coverable if it has an m -covering. An m -covering M such that M is minimum is called an excessive m -factorization of G and the number of matchings it contains is a graph parameter called excessive m -index and denoted by X m G the value of x m G is conventionally set to TO if G is not m -coverable . It is obvious that X 1 G E G for every graph G and it is not difficult to see that X 2 G max x G E G 2 for every 2 -coverable graph G. However the task of determining X m G for arbitrary m and G seems to increase very rapidly in difficulty as m increases and a general formula for m 3 is unknown. In this paper we determine such a formula for m 3 thereby determining the excessive 3 -index for all graphs. Keywords excessive m -index excessive m -factorization matching edge coloring Corresponding author THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R124 1 1 Introduction All graphs considered in this paper will be implicitly assumed to be simple finite undirected and to contain at least one edge and no isolated vertices. The vertex set edge set and maximum degree of a graph G are denoted by V G E G and A G respectively. If Vi c V G we denote by Vi the subgraph of G induced by V1. If E1 c E G we denote by E1 the graph induced by the endpoints of the edges in E1 notice that this graph may contains also edges which are not in E1 . If E1 e f consists of two edges only we use the shorthand e f instead of e