A graph structure is a useful tool in solving the combinatorial problems in different areas of computer science and computational intelligence systems. In this paper, we introduce the concept of ...cubic graph, which is different from the notion of cubic graph in S. Rashid, N. Yaqoob, M. Akram, M. Gulistan, Cubic graphs with application, Int. J. Anal. Appl. 16 (2018), 733–750, and investigate some of their interesting properties. Then we define the notions of cubic path, cubic cycle, cubic diameter, strength of cubic graph, complete cubic graph, strong cubic graph and illustrate these notions by several examples. We prove that any cubic bridge is strong and we investigate equivalent condition for cubic cutvertex. Finally, we use the concept of cubic graphs in traffic flows to get the least time to reach the destination.
Let i be a positive integer. A complete bipartite graph K1,i is called an i-star, denoted by Si. An {S2,S3}-packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each ...subgraph is a 2-star or a 3-star. The maximum {S2,S3}-packing problem is to find an {S2,S3}-packing of a given graph containing the maximum number of vertices. The perfect {S2,S3}-packing problem is to answer whether there is an {S2,S3}-packing containing all vertices of the given graph. The perfect {S2,S3}-packing problem is NP-complete in general graphs. In this paper, we prove that the perfect {S2,S3}-packing problem remains NP-complete in cubic graphs and that every simple cubic graph has an {S2,S3}-packing covering at least six-sevenths of its vertices. Our proof infers a quadratic-time algorithm for finding such an {S2,S3}-packing of a simple cubic graph.
•Determining whether a cubic graph has a perfect 2,3-star-packing is NP-complete.•Every simple cubic graph has a packing covering at least 6/7 of its vertices.•A quadratic-time algorithm for finding such a packing of a simple cubic graph.
Decycling cubic graphs Nedela, Roman; Seifrtová, Michaela; Škoviera, Martin
Discrete mathematics,
August 2024, Letnik:
347, Številka:
8
Journal Article
Recenzirano
A set of vertices of a graph G is said to be decycling if its removal leaves an acyclic subgraph. The size of a smallest decycling set is the decycling number of G. Generally, at least ⌈(n+2)/4⌉ ...vertices have to be removed in order to decycle a cubic graph on n vertices. In 1979, Payan and Sakarovitch proved that the decycling number of a cyclically 4-edge-connected cubic graph of order n equals ⌈(n+2)/4⌉. In addition, they characterised the structure of minimum decycling sets and their complements. If n≡2(mod4), then G has a decycling set which is independent and its complement induces a tree. If n≡0(mod4), then one of two possibilities occurs: either G has an independent decycling set whose complement induces a forest of two trees, or the decycling set is near-independent (which means that it induces a single edge) and its complement induces a tree. In this paper we strengthen the result of Payan and Sakarovitch by proving that the latter possibility (a near-independent set and a tree) can always be guaranteed. Moreover, we relax the assumption of cyclic 4-edge-connectivity to a significantly weaker condition expressed through the canonical decomposition of 3-connected cubic graphs into cyclically 4-edge-connected ones. Our methods substantially use a surprising and seemingly distant relationship between the decycling number and the maximum genus of a cubic graph.
Let H and G be graphs. An H-colouring of G is a proper edge-colouring f:E(G)→E(H) such that for any vertex u∈V(G) there exists a vertex v∈V(H) with f∂Gu=∂Hv, where ∂Gu and ∂Hv respectively denote the ...sets of edges in G and H incident to the vertices u and v. If G admits an H-colouring we say that H colours G. The question whether there exists a graph H that colours every bridgeless cubic graph is addressed directly by the Petersen Colouring Conjecture, which states that the Petersen graph colours every bridgeless cubic graph. In 2012, Mkrtchyan showed that if this conjecture is true, the Petersen graph is the unique connected bridgeless cubic graph H which can colour all bridgeless cubic graphs. In this paper we extend this and show that if we were to remove all degree conditions on H, every bridgeless cubic graph G can be coloured substantially only by a unique other graph: the subcubic multigraph S4 on four vertices. A few similar results are provided also under weaker assumptions on the graph G. In the second part of the paper, we also consider H-colourings of regular graphs having degree strictly greater than 3 and show that: (i) for any r>3, there does not exist a connected graph H (possibly containing parallel edges) that colours every r-regular multigraph, and (ii) for every r>1, there does not exist a connected graph H (possibly containing parallel edges) that colours every 2r-regular simple graph.
Partial domination in supercubic graphs Bujtás, Csilla; Henning, Michael A.; Klavžar, Sandi
Discrete mathematics,
January 2024, 2024-01-00, Letnik:
347, Številka:
1
Journal Article
Recenzirano
Odprti dostop
For some α with 0<α≤1, a subset X of vertices in a graph G of order n is an α-partial dominating set of G if the set X dominates at least α×n vertices in G. The α-partial domination number pdα(G) of ...G is the minimum cardinality of an α-partial dominating set of G. In this paper partial domination of graphs with minimum degree at least 3 is studied. It is proved that if G is a graph of order n and with δ(G)≥3, then pd78(G)≤13n. If in addition n≥60, then pd910(G)≤13n, and if G is a connected cubic graph of order n≥28, then pd1314(G)≤13n. Along the way it is shown that there are exactly four connected cubic graphs of order 14 with domination number 5.
A conjecture of Berge predicts that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. If the graph in question has no 3-edge-colouring, then at least four ...perfect matchings are necessary. It was proved by Esperet and Mazzuoccolo (2014) 3 that it is NP-complete to decide whether four perfect matchings are enough to cover the edges of a bridgeless cubic graph. A disadvantage of the proof (noted by the authors) is that the constructed graphs have 2-cuts. In this paper we show that small cuts can be altogether avoided and that the problem remains NP-complete even for nontrivial snarks – that is, cyclically 4-edge-connected cubic graphs with no 3-edge-colouring. As a by-product, we provide a rich family of nontrivial snarks that cannot be covered with four perfect matchings. The methods rely on the theory of tetrahedral flows developed in Máčajová and Škoviera (2021) 9.
For a graph G, a function f:V(G)→{0,1,2} is called a 2-limited dominating broadcast on G if for every vertex u, there exists a vertex v such that f(v)>0 and the distance between u and v in G is at ...most f(v). The cost of f means the value ∑v∈V(G)f(v), and the 2-limited broadcast domination numberγb,2(G) of G is the cost of a 2-limited dominating broadcast on G with minimum cost. Henning, MacGillivray and Yang (2020) conjectured that γb,2(G)≤|V(G)|3 for every cubic graph G, and then confirmed it for a cubic graph G having neither C4 nor C6 as an induced subgraph. In this paper, we improve their result, that is, we show that the conjecture holds for cubic graphs having no C4 as an induced subgraph.
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least i+1. It ...is proved that in the class of subcubic graphs the packing chromatic number is bigger than 13, thus answering an open problem from Gastineau and Togni (2016). In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if Se(G) is the graph obtained from a graph G by subdividing its edge e, then χρ(G)∕2+1≤χρ(Se(G))≤χρ(G)+1.
PDF
