A study on cubic graphs with novel application Rashmanlou, Hossein; Muhiuddin, G.; Amanathulla, SK ...
Journal of intelligent & fuzzy systems,
01/2021, Letnik:
40, Številka:
1
Journal Article
Recenzirano
Theoretical concepts of graphs are highly utilized by computer science applications. Especially in research areas of computer science such as data mining, image segmentation, clustering, image ...capturing and networking. The cubic graphs are more flexible and compatible than fuzzy graphs due to the fact that they have many applications in networks. In this paper, we define the direct product, strong product, and degree of a vertex in cubic graphs and investigate some of their properties. Likewise, we introduce the notion of complete cubic graphs and present some properties of self complementary cubic graphs. Finally, We present fuzzy cubic organizational model as an example of cubic digraph in decision support system.
The signed double Roman domination problem is a combinatorial optimization problem on a graph asking to assign a label from {±1,2,3} to each vertex feasibly, such that the total sum of assigned ...labels is minimized. Here feasibility is given whenever (i) vertices labeled ±1 have at least one neighbor with label in {2,3}; (ii) each vertex labeled −1 has one 3-labeled neighbor or at least two 2-labeled neighbors; and (iii) the sum of labels over the closed neighborhood of any vertex is positive. The cumulative weight of an optimal labeling is called signed double Roman domination number (SDRDN). In this work, we first consider the problem on general cubic graphs of order n for which we present a sharp n/2+Θ(1) lower bound for the SDRDN by means of the discharging method. Moreover, we derive a new best upper bound. Observing that we are often able to minimize the SDRDN over the class of cubic graphs of a fixed order, we then study in this context generalized Petersen graphs for independent interest, for which we propose a constraint programming guided proof. We then use these insights to determine the SDRDNs of subcubic 2×m grid graphs, among other results.
•Lower and upper bounds for the Signed Double Roman Domination Number (SDRDN) on cubic graphs are strengthened.•Tight/optimal bounds on the SDRDN are established for specific classes of (sub)cubic graphs.•A constraint programming based technique to calculate the SDRDN on rotationally symmetric graphs is proposed.
The resistance of a cubic graph is the smallest number of edges whose removal produces a 3-edge-colourable graph. The flow resistance is the minimum number of zeros in an integer 4-flow on the graph. ...Fiol et al. (2018) made a conjecture that the flow resistance of a bridgeless cubic graph never exceeds its resistance. The conjecture has recently been proved to be false by displaying a family of nontrivial snarks with resistance n and flow resistance 2n (Allie et al., 2022). In this paper, we strengthen the result by showing that the ratio of the flow resistance to the resistance of a snark can be arbitrarily large.
Packing chromatic number of cubic graphs Balogh, József; Kostochka, Alexandr; Liu, Xujun
Discrete mathematics,
February 2018, 2018-02-00, Letnik:
341, Številka:
2
Journal Article
Recenzirano
A packingk-coloring of a graph G is a partition of V(G) into sets V1,…,Vk such that for each 1≤i≤k the distance between any two distinct x,y∈Vi is at least i+1. The packing chromatic number, χp(G), ...of a graph G is the minimum k such that G has a packing k-coloring. Sloper showed that there are 4-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed k and g≥2k+2, almost every n-vertex cubic graph of girth at least g has the packing chromatic number greater than k.
Isomorphic bisections of cubic graphs Das, S.; Pokrovskiy, A.; Sudakov, B.
Journal of combinatorial theory. Series B,
November 2021, 2021-11-00, Letnik:
151
Journal Article
Recenzirano
Odprti dostop
Graph partitioning, or the dividing of a graph into two or more parts based on certain conditions, arises naturally throughout discrete mathematics, and problems of this kind have been studied ...extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs.
Unions of perfect matchings in r-graphs Chen, Guantao; Tokar, Nizamettin
Discrete mathematics,
October 2023, 2023-10-00, Letnik:
346, Številka:
10
Journal Article
Recenzirano
An r-regular graph is said to be an r-graph if |∂(X)|≥r for each odd set X⊆V(G), where |∂(X)| denotes the set of edges with precisely one end in X. Note that every connected bridgeless cubic graph is ...a 3-graph. The Berge Conjecture states that every 3-graph G has five perfect matchings such that each edge of G is contained in at least one of them. Likewise, generalization of the Berge Conjecture asserts that every r-graph G has 2r−1 perfect matchings that covers each e∈E(G) at least once. A natural question to ask in the light of the Generalized Berge Conjecture is that what can we say about the proportion of edges of an r-graph that can be covered by union of t perfect matchings? In this paper we provide a lower bound to this question. We will also present a new conjecture that might help towards the proof of the Generalized Berge Conjecture.
A dominating set in a graph
G is a set
S of vertices such that every vertex in
V
(
G
)
⧹
S is adjacent to a vertex in
S. A restrained dominating set of
G is a dominating set
S with the additional ...restraint that the graph
G
−
S obtained by removing all vertices in
S is isolate‐free. The domination number
γ
(
G
) and the restrained domination number
γ
r
(
G
) are the minimum cardinalities of a dominating set and restrained dominating set, respectively, of
G. Let
G be a cubic graph of order
n. A classical result of Reed states that
γ
(
G
)
≤
3
8
n, and this bound is best possible. To determine the best possible upper bound on the restrained domination number of
G is more challenging, and we prove that
γ
r
(
G
)
≤
2
5
n.
For 1≤s1≤s2≤…≤sk and a graph G, a packing(s1,s2,…,sk)-coloring of G is a partition of V(G) into sets V1,V2,…,Vk such that, for each 1≤i≤k the distance between any two distinct x,y∈Vi is at least ...si+1. The packing chromatic number, χp(G), of a graph G is the smallest k such that G has a packing (1,2,…,k)-coloring. It is known that there are trees of maximum degree 4 and subcubic graphs G with arbitrarily large χp(G). Recently, there was a series of papers on packing (s1,s2,…,sk)-colorings of subcubic graphs in various classes. We show that every 2-connected subcubic outerplanar graph has a packing (1,1,2)-coloring and every subcubic outerplanar graph is packing (1,1,2,4)-colorable. Our results are sharp in the sense that there are 2-connected subcubic outerplanar graphs that are not packing (1,1,3)-colorable and there are subcubic outerplanar graphs that are not packing (1,1,2,5)-colorable. We also show subcubic outerplanar graphs that are not packing (1,2,2,4)-colorable and not packing (1,1,3,4)-colorable.
Let G be a simple connected graph with vertex set V(G) and edge set E(G). The resistance distance r(u,v) between two vertices u,v∈V(G) is the net effective resistance between them in the electric ...network constructed from G by replacing each edge with a unit resistor. This function is known to be a metric on the vertex-set of any graph. The sum of resistance distances between pairs of vertices in a G is called Kirchhoff index and is denoted by Kf(G). In this study, we will compute the resistance distance between pairs of vertices of string of diamonds and ring of diamonds by using some methods from electrical network theory such as series and parallel principles, the principle of elimination, the star-triangle transformation, and the delta-wye transformation. Then we determine the exact formulas for the Kirchhoff index of the string of diamonds and ring of diamonds.
A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number, i(G), of G ...is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i(G)≤411n. We show that the bipartite condition can be relaxed, and prove that if G is a cubic graph of order n and of girth at least 6, then i(G)≤411n.
PDF
