Research on Fractional Critical Covered Graphs
- PDF / 346,230 Bytes
- 8 Pages / 612 x 792 pts (letter) Page_size
- 46 Downloads / 165 Views
RGE SYSTEMS
Research on Fractional Critical Covered Graphs S. Wanga, ∗ and W. Zhangb a
School of Public Management, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu, China b Oujiang College, Wenzhou University, Wenzhou, Zhejiang, China e-mail : ∗ [email protected] Received November 11, 2019; revised May 13, 2020; accepted June 12, 2020 Abstract—A graph G is called a fractional (g, f )-covered graph if for any e ∈ E(G), G admits a fractional (g, f )-factor covering e. A graph G is called a fractional (g, f, n)-critical covered graph if for any S ⊆ V (G) with |S| = n, G − S is a fractional (g, f )-covered graph. A fractional (g, f, n)-critical covered graph is said to be a fractional (a, b, n)-critical covered graph if g(x) = a and f (x) = b for every x ∈ V (G). A fractional (a, b, n)-critical covered graph was first defined and studied in [1]. In this article, we investigate fractional (g, f, n)-critical covered graphs and present a binding number condition for the existence of fractional (g, f, n)-critical covered graphs, which is an improvement and generalization of a previous result obtained in [2]. Key words: graph, binding number, fractional (g, f )-factor, fractional (g, f )-covered graph, fractional (g, f, n)-critical covered graph. DOI: 10.1134/S0032946020030047
1. INTRODUCTION Many real-world networks can conveniently be modeled by graphs. Vertices of the graph stand for nodes of the network, and edges of the graph act for links between the nodes in the network. Next we give some examples: a communication network with nodes acting for cities and links standing for communication channels, or an online social network with nodes representing persons and links corresponding to personal contacts of each user, or the World Wide Web with nodes corresponding to web pages and links modeling hyperlinks between web pages. Henceforth, we use the term graph instead of network. Network science (also known as complex network analysis) is an emerging area of interest in the big data paradigm which analyzes complex real-world networks and theoretical model-based networks from a graph theory point of view. The problem of fractional factor can be thought over as a relaxation of the well-known cardinality matching problem and possesses extensive applications in many related fields such as network design, scheduling, and the combinatorial polyhedron. For example, several large data packets can be sent to various destinations by means of several channels in a communication network. The efficiency of this network can be improved if large data packets can be partitioned into small parcels. The feasible assignment of data packets can be regarded as a fractional flow problem, and it becomes a fractional factor problem when the destinations and sources of a network are disjoint [3]. In the graph theory model, we remove vertices of a graph corresponding to damaged sites of a network. Edges of the resulting graph correspond to links of the resulting network. We now seek the fractional factor via special edges in the res
Data Loading...
