Filters
total: 13
Search results for: cubic graph

Tighter bounds on the size of a maximum P3matching in a cubic graph
PublicationW pracy pokazano, że największe P3skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.

On bipartization of cubic graphs by removal of an independent set
PublicationWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.

Total Domination Versus Domination in Cubic Graphs
PublicationA dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

Packing ThreeVertex Paths in 2Connected Cubic Graphs
PublicationW pracy rozważano problem rozmieszczanie ścieżek P3 w 2spójnych grafach 3regularnych. Pokazano, że w 2spójnym grafie 3regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.

Equitable and semiequitable coloring of cubic graphs and its application in batch scheduling
PublicationIn the paper we consider the problems of equitable and semiequitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semiequitable coloring is NP complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unitlength jobs with cubic incompatibility graph on three uniform processors to minimize...

Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublicationA graph is equitably kcolorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...

Equitable and semiequitable coloring of cubic graphs and its application in batch scheduling
Publication 
Scheduling of unitlength jobs with cubic incompatibility graphs on three uniform machines
PublicationWe consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2chromatic then the problem can be solved in O(n^2) time. If the graph is 3chromatic, the problem becomes NPhard even if s1>s2=s3.

Sharp bounds for the complexity of semiequitable coloring of cubic and subcubic graphs
PublicationIn this paper we consider the complexity of semiequitable kcoloring of the vertices of a cubic or subcubic graph. We show that, given nvertex subcubic graph G, a semiequitable kcoloring of G is NPhard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.

Tight bounds on the complexity of semiequitable coloring of cubic and subcubic graphs
PublicationWe consider the complexity of semiequitable kcoloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a nvertex subcubic graph G, it is NPcomplete to obtain a semiequitable kcoloring of G whose nonequitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.

Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych
PublicationW pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NPzupełny w szerokim zakresie parametrów grafów.

Polynomial Algorithm for Minimal (1,2)Dominating Set in Networks
PublicationDominating sets find application in a variety of networks. A subset of nodes D is a (1,2)dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NPhard. In this paper, we...

Uniform expansion estimates in the cubic map as a function of the parameter
Open Research DataThis dataset contains selected results of numerical computations described in the paper "Quantitative hyperbolicity estimates in onedimensional dynamics" by S. Day, H. Kokubu, S. Luzzatto, K. Mischaikow, H. Oka, P. Pilarczyk, published in Nonlinearity, Vol. 21, No. 9 (2008), 19671987, doi: 10.1088/09517715/21/9/002.