Search

Let G be a simple graph of order n. Let S be a coloring subset of V (G). The forcing process is that a colored vertex forces the uncolored neighbor to be colored if it has exactly one uncolored neighbor. The set S is a zero forcing set if all vertices of G become colored by iteratively applying the forcing process. The minimum size of a zero forcing set in a graph G is zero forcing number, denoted by Z (G) , which is proposed in 2008 as a natural upper bound of the maximum nullity regarding the graph G. In the paper, we bound the zero forcing number in connected claw-free cubic graphs. More exactly if G (≠ K 4) is a connected claw-free cubic graph with order n , then we prove that Z (G) ≤ α (G) except for three graphs with small order, and then Z (G) ≤ n 4 + 1 except for three classes of graphs. In fact, our results give affirmative answers for two open problems raised by Davila and Henning. [ABSTRACT FROM AUTHOR]

A b-greedy colouring is a colouring which is both a b-colouring and a greedy colouring. A z-colouring is a b-greedy colouring such that a b-vertex of the largest colour is adjacent to a b-vertex of every other colour. The b-Grundy number (resp. z-number) of a graph is the maximum number of colours in a b-greedy colouring (resp. z-colouring) of it. In this paper, we study those two parameters. We show that similarly to the z-number, the b-Grundy number is not monotone and can be arbitrarily smaller than the minimum of the Grundy number and the b-chromatic number. We also describe a polynomial-time algorithm that decides whether a given k -regular graph has b-Grundy number (resp. z-number) equal to k + 1. We also prove that every cubic graph with no induced 4-cycle has b-Grundy number and z-number exactly 4. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Zhejiang University (Science Edition) is the property of Journal of Zhejiang University (Science Edition) Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Given a simple, finite graph with vertex set V(G), we define a zero forcing set of G as follows. Choose S ⊆ V (G) and color all vertices of S blue and all vertices in V (G) - S white. The color change rule is if w is the only white neighbor of blue vertex v, then we change the color of w from white to blue. If after applying the color change rule as many times as possible eventually every vertex of G is blue, we call S a zero forcing set of G. Z(G) denotes the minimum cardinality of a zero forcing set. We show that if G is 2-edge-connected, claw-free, and cubic, then. We also study a similar graph invariant known as the loop zero forcing number of a graph G which happens to be the dual invariant to the Grundy domination number of G. Specifically, we study the loop zero forcing number in two particular types of planar graphs. [ABSTRACT FROM AUTHOR]

For non-decreasing sequence of integers (a 1 , a 2 , ... , a k) , an (a 1 , a 2 , ... , a k) -packing coloring of G is a partition of V (G) into k subsets V 1 , V 2 , ... , V k such that the distance between any two vertices x , y ∈ V i is at least a i + 1 , 1 ≤ i ≤ k. Yang and Wu (2023) proved that every 3-irregular subcubic graph is (1 , 1 , 3) -packing colorable. We introduce here a simpler and shorter proof of this result. [ABSTRACT FROM AUTHOR]

Let r≥2 $r\ge 2$ be a real number. A complex nowhere‐zero r $r$‐flow on a graph G $G$ is an orientation of G $G$ together with an assignment φ:E(G)→C $\varphi :E(G)\to {\mathbb{C}}$ such that, for all e∈E(G) $e\in E(G)$, the Euclidean norm of the complex number φ(e) $\varphi (e)$ lies in the interval [1,r−1] $[1,r-1]$ and, for every vertex, the incoming flow is equal to the outgoing flow. The complex flow number of a bridgeless graph G $G$, denoted by ϕC(G) ${\phi }_{{\mathbb{C}}}(G)$, is the minimum of the real numbers r $r$ such that G $G$ admits a complex nowhere‐zero r $r$‐flow. The exact computation of ϕC ${\phi }_{{\mathbb{C}}}$ seems to be a hard task even for very small and symmetric graphs. In particular, the exact value of ϕC ${\phi }_{{\mathbb{C}}}$ is known only for families of graphs where a lower bound can be trivially proved. Here, we use geometric and combinatorial arguments to give a nontrivial lower bound for ϕC(G) ${\phi }_{{\mathbb{C}}}(G)$ in terms of the odd‐girth of a cubic graph G $G$ (i.e., the length of a shortest odd cycle) and we show that this lower bound is tight. This result relies on the exact computation of the complex flow number of the wheel graph Wn ${W}_{n}$. In particular, we show that for every odd n $n$, the value of ϕC(Wn) ${\phi }_{{\mathbb{C}}}({W}_{n})$ arises from one of three suitable configurations of points in the complex plane according to the congruence of n $n$ modulo 6. [ABSTRACT FROM AUTHOR]

Given a non-decreasing sequence S = (s 1 , s 2 , ... , s k) of positive integers, an S -packing coloring of a graph G is a partition of the vertex set of G into k subsets { V 1 , V 2 , ... , V k } such that for each 1 ≤ i ≤ k , the distance between any two distinct vertices u and v in V i is at least s i + 1. In this paper, we study the problem of S -packing coloring of cubic Halin graphs, and we prove that every cubic Halin graph is (1 , 1 , 2 , 3) -packing colorable. In addition, we prove that such graphs are (1 , 2 , 2 , 2 , 2 , 2) -packing colorable. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RDF) on a graph G is a function f : V (G) → { 0 , 1 , 2 } such that every vertex u ∈ V (G) with f (u) = 0 is adjacent to at least one vertex v ∈ V (G) with f (v) = 2. An independent Roman dominating function (IRDF) f on a graph G is a Roman dominating function such that the set of vertices u ∈ V (G) with f (u) ∈ { 1 , 2 } form an independent set on G. The weight of f is f (V (G)) = ∑ v ∈ V (G) f (v). The minimum weight of an RDF (IRDF) on G is the Roman domination number (independent Roman domination number) of G , denoted by γ R (G) ( i R (G)). The (independent) Roman domination problem asks for an (independent) Roman dominating function with minimum weight. In this work, we prove that the decision version of the (independent) Roman domination problem is NP -complete even when restricted to planar bipartite graphs with maximum degree three. Moreover, we study the (independent) Roman domination number on three infinite families of snarks. More specifically, we determine the (independent) Roman domination number for generalized Blanuša snarks and we present lower and upper bounds for the (independent) Roman domination number of Goldberg snarks and Loupekine Snarks. [ABSTRACT FROM AUTHOR]

A graph G is equitably k-colorable 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 integer k for which such a coloring exists is known as the equitable chromatic number of G and it is denoted by x=( G). In this paper the problem of determining the value of equitable chromatic number for multicoronas of cubic graphs G◦ lH is studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for these graphs. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use at most x=( G◦ lH) + 1 colors in the remaining cases.

The Strip-Plot Design (SPD) is plays an important role in the complete block designs and also using the agricultural, medical and industry fields. SPD is best suited for a two-factor experiment that has more treatments than can be accommodated by a complete block design. In a SPD, one factor is assigned to the horizontal strip plot, one factor is assigned to the vertical - strip plot and one factor is interaction plot. Also, few experimental materials may be rare while other test items may be available in altering doses of other therapeutic factors, which may be expensive or time-consuming. One of the main features of SPD involves three types of experimental errors: row - strip plot error, coloum - strip plot error and interaction plot error. Experimenting across processing steps is essential for studying the interaction of factors where certain factors come from one step and others arrive from the other. The strip-plot design is a very efficient design for investigating multiple-step processes in terms of both resources and time. Strip-plot designs are economical when the factors are hard to change and the process under research has three discrete stages. When we want to study interactions between factors where some factors are from one step and other factors from another step, it is important to conduct experiments across processing steps. The approach is flexible because it can handle experimental design problems involving factors acting at different levels, unlike the existing method. Graphs are widely used representations of both natural and human-made structures. Graph theory can be used to investigate "things that are connected to other things. "Fits nearly everywhere. Some tough problems become easier to solve when they are represented graphically. We reviewed the agricultural field yield of the strip-plot design and early work on the design of industrial strip-plot design in this paper. We have also described the model of strip-plot design. We, therefore, advise experimenters to ensure that their strip-plot designs contain a sufficient number of rows and columns so that valid statistical inference is possible. A bipartite graph is one in which the edges can be divided into two sets without going into sets. A complete bipartite graph is a bipartite graph that is completed. The complete tripartite graph in which the edges can be divided into three set without going into sets. The cubic graph is a graph in which all vertices have degree three. This paper describes the construction and Statistical Analysis of SPD using some particular types of graphs is discussed through numerical examples. [ABSTRACT FROM AUTHOR]

Let P 4 denote the path on four vertices. A P 4 -packing of a graph G is a collection of vertex-disjoint copies of P 4 in G. The maximum P 4 -packing problem is to find a P 4 -packing of maximum cardinality in a graph. In this paper, we prove that every simple cubic graph G on v(G) vertices has a P 4 -packing covering at least 2 v (G) 3 vertices of G and that this lower bound is sharp. Our proof provides a quadratic-time algorithm for finding such a P 4 -packing of a simple cubic graph. [ABSTRACT FROM AUTHOR]

We consider the class of 2-connected cubic graphs having only k-cycles in each 2-factor, and obtain the following two results: (i) every 2-connected cubic graph having only 8-cycles in each 2-factor is isomorphic to a unique Hamiltonian graph of order 8; and (ii) a 2-connected cubic planar graph G has only k-cycles in each 2-factor if and only if k = 4 and G is the complete graph of order 4. [ABSTRACT FROM AUTHOR]

A graph Gis equitably k-colorable if its vertices can be partitioned into kindependent sets in such a way that the number of vertices in any two sets differby at most one. The smallest integer k for which such a coloring exists is knownas the equitable chromatic number of Gand it is denoted by χ=(G). In this paper the problem of determinig the value of equitable chromaticnumber for multicoronas of cubic graphs GolHis studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for thesegraphs. We provide some polynomially solvable cases of cubical multicoronasand give simple linear time algorithms for equitable coloring of such graphswhich use at most χ=(GolH) + 1 colors in the remaining cases. [ABSTRACT FROM AUTHOR]

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 ∂ G u = ∂ H v , where ∂ G u and ∂ H v 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 S 4 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 2 r -regular simple graph. [ABSTRACT FROM AUTHOR]

Given a graph G $G$, a dominating set of G $G$ is a set S $S$ of vertices such that each vertex not in S $S$ has a neighbor in S $S$. Let γ(G) $\gamma (G)$ denote the minimum size of a dominating set of G $G$. The independent domination number of G $G$, denoted i(G) $i(G)$, is the minimum size of a dominating set of G $G$ that is also independent. We prove that if G $G$ is a cubic graph without 4‐cycles, then i(G)≤514∣V(G)∣ $i(G)\le \frac{5}{14}| V(G)| $, and the bound is tight. This result improves upon two results from two papers by Abrishami and Henning. Our result also implies that every cubic graph G $G$ without 4‐cycles satisfies i(G)γ(G)≤54 $\frac{i(G)}{\gamma (G)}\le \frac{5}{4}$, which supports a question asked by O and West. [ABSTRACT FROM AUTHOR]

Let G ${\mathscr{G}}$ be a class of graphs with a membership test, k∈N $k\in {\mathbb{N}}$, and let Gk ${{\mathscr{G}}}^{k}$ be the class of graphs in G ${\mathscr{G}}$ of path‐width at most k $k$. We present an interactive framework that finds an unavoidable set for Gk ${{\mathscr{G}}}^{k}$, which is a set of graphs U ${\mathscr{U}}$ such that any graph in Gk ${{\mathscr{G}}}^{k}$ contains an isomorphic copy of a graph in U ${\mathscr{U}}$. At the core of our framework is an algorithm that verifies whether a set of graphs is, indeed, unavoidable for Gk ${{\mathscr{G}}}^{k}$. While obstruction sets are well‐studied, so far there is no general theory or algorithm for finding unavoidable sets. In general, it is undecidable whether a finite set of graphs is unavoidable for a given graph class. However, we give a criterion for termination: our algorithm terminates whenever G ${\mathscr{G}}$ is locally checkable of bounded maximum degree and U ${\mathscr{U}}$ is a finite set of connected graphs. For example, l $l$‐regular graphs, l $l$‐colourable graphs, and H $H$‐free graphs are locally checkable classes. We put special emphasis on the case that G ${\mathscr{G}}$ is the class of cubic graphs and tailor the algorithm to this case. In particular, we introduce the new concept of high‐degree‐first path‐decompositions, which enables highly efficient pruning techniques. We exploit our framework to prove a new lower bound on the path‐width of cubic graphs. Moreover, we determine the extremal girth values of cubic graphs of path‐width k $k$ for all k∈{3,...,10} $k\in \{3,\ldots ,10\}$ and all smallest graphs which take on these extremal girth values. Further, we present a new constructive characterisation of the extremal cubic graphs of path‐width 3 and girth 4. [ABSTRACT FROM AUTHOR]

The independence number α(G) $\alpha (G)$ and the dissociation number diss(G) $\text{diss}(G)$ of a graph G $G$ are the largest orders of induced subgraphs of G $G$ of maximum degree at most 0 and at most 1, respectively. We consider possible improvements of the obvious inequality 2α(G)≥diss(G) $2\alpha (G)\ge \text{diss}(G)$. For connected cubic graphs G $G$ distinct from K4 ${K}_{4}$, we show 5α(G)≥3diss(G) $5\alpha (G)\ge 3\,\text{diss}(G)$, and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle‐free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs. [ABSTRACT FROM AUTHOR]

Among some results, we prove the following two theorems. (i) Let G be a connected claw-free graph. We arbitrarily color every vertex of G red or blue so that the number of red vertices is even. Then G has vertex-disjoint paths whose end-vertices are exactly the same as the red vertices of G. (ii) Let G be a 3-edge connected claw-free cubic graph. We arbitrarily color every vertex of G red or blue so that the number of red vertices is even and the distance between any two red vertices is at least 3. Then G has a factor F such that deg F (x) = 1 for every red vertex x and deg F (y) = 2 for every blue vertex y. [ABSTRACT FROM AUTHOR]

The average distance μ(G) $\mu (G)$ of a simple connected graph G $G$ is the average of the distances between all pairs of vertices in G $G$. We prove that for a connected cubic graph G $G$ on n $n$ vertices, μ(G)≤n3−16n+484(n2−n) $\mu (G)\le \frac{{n}^{3}-16n+48}{4({n}^{2}-n)}$, if n=4k+2 $n=4k+2$; and μ(G)≤n3−32n+1284(n2−n) $\mu (G)\le \frac{{n}^{3}-32n+128}{4({n}^{2}-n)}$, if n=4k+4 $n=4k+4$. Furthermore, all extremal graphs attaining the upper bounds are characterized, and they have the maximum possible diameter. The result solves a question of Plesník and proves a conjecture of Knor, Škrekovski, and Tepeh on the average distance of cubic graphs. The proofs use graph transformations and structural graph analysis. [ABSTRACT FROM AUTHOR]

Connectivity is one of the most important parameters related to networks such as internet routing, transport network flow, and so on, which can be used to measure the stability of a network. This concept has particular importance in fuzzy graphs. A cubic fuzzy graph is a fuzzy graph that supports both fuzzy membership and interval-valued fuzzy membership. Simultaneity of two different memberships leads to better flexibility in modeling problems than uncertain variables. The limitations of previous definitions in this area led to the description of connectivity indices in a cubic fuzzy graph. In this research work, the parameters of connectivity index and average connectivity index are described as the main parameters related to the network. Some of their properties and boundaries have been studied. The results of removing a vertex and its effect on the connectivity index are discussed. Finally, an application of connectivity index in an interconnected network of journals is presented. [ABSTRACT FROM AUTHOR]

In this paper, we find a special type of non-traceable cubic bridge graph called well-formed graph whose central fragment is isomorphic to a hairy cycle and whose branches are pairwise isomorphic. We then show that a well-formed graph can be partition into isomorphic subgraph. Some properties of a well-formed graph such as perfect matching, matching number, decomposition and some parameters for pictorial representation are also provided. [ABSTRACT FROM AUTHOR]

A strong edge-coloring of a graph G is an edge-coloring of G such that any two edges that are either adjacent to each other or adjacent to a common edge receive distinct colors. The strong chromatic index of G, denoted by χ s ′ (G) , is the minimum number of colors needed to guarantee that G admits a strong edge-coloring. For any integer n ≥ 3 , let H n denote the n-prism (i.e., the Cartesian product C n □ K 2 ) and H n Δ the graph obtained from H n by replacing each vertex with a triangle. Recently, Lin and Lin (2022) asked whether χ s ′ (H n Δ) = 6 for any n ≥ 3 . In this short note, we answer this question in the affirmative. [ABSTRACT FROM AUTHOR]

Let G be a bridgeless cubic graph. The Berge–Fulkerson Conjecture (1970s) states that G admits a list of six perfect matchings such that each edge of G belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan–Raspaud Conjecture (1994), which states that G admits three perfect matchings such that every edge of G belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that G admits two perfect matchings whose deletion yields a bipartite subgraph of G. It can be shown that given an arbitrary perfect matching of G , it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan–Raspaud and the Berge–Fulkerson conjectures, respectively. In this paper, we show that given any 1 + -factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G , there always exists a perfect matching M of G containing e such that G ∖ (F ∪ M) is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in G , there exists a perfect matching of G containing at least one edge of each circuit in this collection. [ABSTRACT FROM AUTHOR]

A fullerene graph is a planar, cubic, 3-connected graph with only pentagonal and hexagonal faces. In 2012, Andova and Škrekovski conjectured that the diameter of every fullerene graph with n vertices is at least √5 n /3 - 1. They computed this lower bound by studying a particular class of fullerene graphs named spherical with icosahedral symmetry. We denote these graphs by G i,j , by setting two parameters i , j ε N* , such that i ≤ j. In their study, Andova and Škrekovski offered numerous properties of hexagonal lattices and calculated the diameter of two remarkable spherical fullerene graphs: G 0 ,j and G j,j. Although the conjecture is valid for these two distinct classes, it remains open deciding whether the premise is proper for all spherical fullerene graphs G i,j. In this work, we present the first class of fullerene graphs with icosahedral symmetry that do not satisfy Andova and Skrekovski's conjecture, which refutes that this conjecture is valid for all spherical graphs. We also focus on showing properties of spherical fullerene graphs and the hexagonal lattice itself. We prove that all graphs G i,j have a reduction of the form G i-k,j-k , where k ≤ i , such that their triangular faces are entirely contained in the triangular faces of G i,j. In addition, by setting k = i , this property states a particular link among G i,j , G i-1 , j -1, • • • , G 0 ,j - i , creating a chain of reductions of G i,j , which implies that diam (G i,j) ≥ diam (G 0 ,j - i). [ABSTRACT FROM AUTHOR]

Let G be a cubic graph and Π be a polyhedral embedding of this graph. The extended graph, Ge; of Π is the graph whose set of vertices is V (Ge) = V (G) and whose set of edges E(Ge) is equal to E(G) υ S, where S is constructed as follows: given two vertices t0 and t3 in V (Ge) we say [t0t3] ∈ S, if there is a 3-path, (t0t1t2t3) ∈ G that is a Π-facial subwalk of the embedding. We prove that there is a one to one correspondence between the set of possible extended graphs of G and polyhedral embeddings of G. [ABSTRACT FROM AUTHOR]

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 C 4 nor C 6 as an induced subgraph. In this paper, we improve their result, that is, we show that the conjecture holds for cubic graphs having no C 4 as an induced subgraph. [ABSTRACT FROM AUTHOR]

We show that every claw-free cubic graph of order n at least 8 has at most 2⌊n4⌋{2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs.

A graphical regular representation (GRR) of a group G is a Cayley graph of G whose full automorphism group is equal to the right regular permutation representation of G. In this paper we study cubic GRRs of PSL n (q) (n = 4 , 6 , 8), PSp n (q) (n = 6 , 8), P Ω n + (q) (n = 8 , 10 , 12) and P Ω n − (q) (n = 8 , 10 , 12), where q = 2 f with f ≥ 1. We prove that for each of these groups, with probability tending to 1 as q → ∞ , any element x of odd prime order dividing 2 e f − 1 but not 2 i − 1 for each 1 ≤ i < e f together with a random involution y gives rise to a cubic GRR, where e = n − 2 for P Ω n + (q) and e = n for other groups. Moreover, for sufficiently large q , there are elements x satisfying these conditions, and for each of them there exists an involution y such that { x , x − 1 , y } produces a cubic GRR. This result together with certain known results in the literature implies that except for PSL 2 (q) , PSL 3 (q) , PSU 3 (q) and a finite number of other cases, every finite non-abelian simple group contains an element x and an involution y such that { x , x − 1 , y } produces a GRR, showing that a modified version of a conjecture by Spiga is true. Our results and several known results together also confirm a conjecture by Fang and Xia which asserts that except for a finite number of cases every finite non-abelian simple group has a cubic GRR. [ABSTRACT FROM AUTHOR]

Low-density parity-check (LDPC) codes have been the subject of much interest due to the fact that they can perform near the Shannon limit. In this paper we present a construction of LDPC codes from cubic symmetric graphs. The codes constructed are (3, 3)-regular and the vast majority of the corresponding Tanner graphs have girth greater than four. We analyse properties of the codes obtained and present bounds for the code parameters, the dimension and the minimum distance. Furthermore, we give an expression for the variance of the syndrome weight of the codes constructed. Information on the LDPC codes constructed from bipartite cubic symmetric graphs with less than 200 vertices is presented as well. Some of the codes constructed are optimal, and some have an additional property of being self-orthogonal or linear codes with complementary dual (LCD codes). [ABSTRACT FROM AUTHOR]

A sign-circuit cover F of a signed graph (G , σ) is a family of sign-circuits which covers all edges of (G , σ) . The shortest sign-circuit cover problem was initiated by Má c ˇ ajová, Raspaud, Rollová, and Škoviera (JGT 2016) and received many attentions in recent years. In this paper, we show that every flow-admissible signed 3-edge-colorable cubic graph (G , σ) has a sign-circuit cover with length at most 20 9 | E (G) | . [ABSTRACT FROM AUTHOR]

Graphs considered in this paper are simple finite undirected graph without loops or multiple edges. A simple graph where each vertex has degree 3 is called a cubic graph. A cubic graph, that is, 1-connected or cubic bridge graph is traceable if it contains a Hamiltonian path. Otherwise, we called it non-traceable. In this paper, we introduce a new family of cubic graphs called Non-Traceable Cubic Bridge Graph (NTCBG) that satisfies the conjecture of Zoeram and Yaqubi (2017). In addition, we define two important connected components of NTCBG those are the central fragment that gives assurance for a graph to be non-traceable and its branch. Some properties of a NTCBG such as chromatic number and clique number are also provided. [ABSTRACT FROM AUTHOR]

The transmission of a vertex v of a graph G is the sum of distances from v to all the other vertices of G. A transmission irregular graph (TI graph) has mutually distinct vertex transmissions. In 2018, Alizadeh and Klavžar posed the following question: do there exist infinite families of regular TI graphs? An infinite family of TI cubic graphs of order 118 + 72 k , k ≥ 0 , was constructed by Dobrynin in 2019. In this paper, we study the problem of finding TI cubic graphs for an arbitrary number of vertices. It is shown that there exists a TI cubic graph of an arbitrary even order n ≥ 22 . Almost all constructed graphs are contained in twelve infinite families. [ABSTRACT FROM AUTHOR]

A proper edge coloring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge coloring of a k $k$‐regular graph at least 2k−1 $2k-1$ colors are needed. We show that a k $k$‐regular graph admits a strong edge coloring with 2k−1 $2k-1$ colors if and only if it covers the Kneser graph K(2k−1,k−1) $K(2k-1,k-1)$. In particular, a cubic graph is strongly 5‐edge‐colorable whenever it covers the Petersen graph. One of the implications of this result is that a conjecture about strong edge colorings of subcubic graphs proposed by Faudree et al. is false. [ABSTRACT FROM AUTHOR]

The adequate representation of uncertainty in fuzzy attributes and its approximation is considered as one of the major issues for knowledge processing tasks. To deal with this issue, recently the calculus of cubic set and its mathematical algebra is established. This paper tried to introduce cubic set based formal context and its concept lattice at user defined cubic granulation. The obtained results are compared with recently available approaches with an illustrative example. [ABSTRACT FROM AUTHOR]

The cubic set, introduced as a combination of a fuzzy set and an interval-valued fuzzy set, provided researchers with more flexibility than the previous two sets in dealing with complex and uncertain problems. Fuzzy graphs, based on this type of set, are among the emerging fuzzy graphs that have a great potential to model the surrounding phenomena. Consistent with the special role that cubic graphs play in decision-making and selecting superior options, dominating these graphs is of great importance and value. In this paper, we introduce the domination of the cubic graphs in terms of strong edges and examine their properties. In addition, we examine domination in terms of independent sets and since many of the phenomena surrounding us are hybrid, we also discuss the domination concept on its fuzzy operations. Finally, we present an application of this graph on the subject of domination. [ABSTRACT FROM AUTHOR]

Edge-elimination is an operation of removing an edge of a cubic graph together with its endvertices and suppressing the resulting 2-valent vertices. We study the effect of this operation on the cyclic connectivity of a cubic graph. Disregarding a small number of cubic graphs with no more than six vertices, this operation cannot decrease cyclic connectivity by more than two. We show that apart from three exceptional graphs (the cube, the twisted cube, and the Petersen graph) every 2-connected cubic graph on at least eight vertices contains an edge whose elimination decreases cyclic connectivity by at most one. The proof reveals an unexpected behaviour of connectivity 6, which requires a detailed structural analysis featuring the Isaacs flower snarks and their natural generalisation, the twisted Isaacs graphs, as forced structures. A complete characterisation of this family, which includes the Heawood graph as a sporadic case, serves as the main tool for excluding the existence of exceptional graphs in connectivity 6. As an application we show that every cyclically 5-edge-connected cubic graph has a decycling set of vertices whose removal leaves a tree and the set itself has at most one edge between its vertices. This strengthens a classical result of Payan and Sakarovitch (1975) about the structure of minimum decycling sets in cyclically 4-edge-connected graphs. [ABSTRACT FROM AUTHOR]

Over the past twenty years, critical and bicritical snarks have been appearing in the literature in various forms and in different contexts. Two main variants of criticality of snarks have been studied: criticality with respect to the non-existence of a 3-edge-colouring and criticality with respect to the non-existence of a nowhere-zero 4-flow. In this paper we show that these two kinds of criticality coincide, thereby completing previous partial results of de Freitas et al. [Electron. Notes Discrete Math. 50 (2015) 199–204] and Fiol et al. [Electron. J. Combin. 25 (2017) #P4.54].

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 (mod 4) , then G has a decycling set which is independent and its complement induces a tree. If n ≡ 0 (mod 4) , 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. [ABSTRACT FROM AUTHOR]

A packing in a graph is a set of vertices that are mutually distance at least 3 apart. By using optimization and linear programming to help analyze the greedy algorithm, we improve on a result of Favaron and show that every connected cubic graph of order n has a packing of size at least 17 132 n − O (1). [ABSTRACT FROM AUTHOR]

The perfect m-coloring with matrix A = [aij ]i,j∈{1,···,m} of a graph G = (V, E) with {1, · · ·, m} color is a vertex coloring of G with m-color so that the number of vertices in color j adjacent to a fixed vertex in color i is aij, independent of the choice of vertex in color i. The matrix A = [aij ]i,j∈{1,···,m} is called the parameter matrix. We study the perfect 4-colorings of the 3-regular graphs of order at most 8, that is, we determine a list of all color parameter matrices corresponding to perfect 4-colorings of 3-regular graphs of orders 4, 6, and 8. [ABSTRACT FROM AUTHOR]

Berge Conjecture states that every bridgeless cubic graph has 5 perfect matchings such that each edge is contained in at least one of them. In this paper, we show that Berge Conjecture holds for bridgeless cubic graphs which have two perfect matchings with at most one common edge. [ABSTRACT FROM AUTHOR]

A finite simple graph is called a k-multicirculant if its automorphism group contains a cyclic semiregular subgroup having k orbits on the vertex set. It was shown by Giudici et al. that, if k is squarefree and coprime to 6, then a cubic arc-transitive k-multicirculant has at most 6 k 2 vertices (J. Combin. Theory Ser. B, 2017). In this paper, we classify the latter graphs under the assumption that their semiregular cyclic subgroups are contained in a soluble group of automorphisms acting transitively on the arc set of the graphs. As an application, cubic arc-transitive p-multicirculants are completely described for each odd prime p. [ABSTRACT FROM AUTHOR]

Zero forcing is an iterative graph coloring process that starts with a subset S of "colored" vertices, all other vertices being "uncolored". At each step, a colored vertex with a unique uncolored neighbor forces that neighbor to be colored. If at the end of the forcing process all the vertices of the graph are colored, then the initial set S is called a zero forcing set. If in addition, every vertex in S is within distance 2 of another vertex of S, then S is a semitotal forcing set. The semitotal forcing number F t 2 (G) of a graph G is the cardinality of the smallest semitotal forcing set of G. In this paper, we begin to study basic properties of F t 2 (G) , relate F t 2 (G) to other domination parameters, and establish bounds on the effects of edge operations on the semitotal forcing number. We also investigate the semitotal forcing number for subfamilies of cubic graphs. [ABSTRACT FROM AUTHOR]

It is proved that for n≥6, the number of perfect matchings in a simple connected cubic graph on 2n vertices is at most 4fn−1, with fn being the n‐th Fibonacci number. The unique extremal graph is characterized as well. In addition, it is shown that the number of perfect matchings in any cubic graph G equals the expected value of a random variable defined on all 2‐colorings of edges of G. Finally, an improved lower bound on the maximum number of cycles in a cubic graph is provided. [ABSTRACT FROM AUTHOR]

The vertex-edge domination number of a graph, γve(G), is defined to be the cardinality of a smallest set D such that there exists a vertex cover C of G such that each vertex in C is dominated by a vertex in D. This is motivated by the problem of determining how many guards are needed in a graph so that a searchlight can be shone down each edge by a guard either incident to that edge or at most distance one from a vertex incident to the edge. Our main result is that for any cubic graph G with n vertices, γve(G) ≤ 9n/26. We also show that it is NP-hard to decide if γve(G) = γ(G) for bipartite graph G.