The power domination problem focuses on finding the optimal placement of phase measurement units (PMUs) to monitor an electrical power network. In the context of graphs, the power domination number ...of a graph G, denoted γP(G), is the minimum number of vertices needed to observe every vertex in the graph according to a specific set of observation rules. In 15, Zhao et al. proved that if G is a connected claw-free cubic graph of order n, then γP(G)≤n/4. In this paper, we show that if G is a claw-free diamond-free cubic graph of order n, then γP(G)≤n/6, and this bound is sharp. We also provide new bounds on γP(G□H) where G□H is the Cartesian product of graphs G and H. In the specific case that G and H are trees whose power domination number and domination number are equal, we show the Vizing-like inequality holds and γP(G□H)≥γP(G)γP(H).
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.
Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components G1 and G2. We prove that each component Gi can be completed to a cyclically 5-connected cubic ...graph by adding three vertices, unless Gi is a cycle of length five. Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1988.
A cubic graph Γ is called G-symmetric if a group G of automorphisms of Γ acts transitively on the arcs of Γ, and G-basic if it is G-symmetric and G has no non-trivial normal subgroups with more than ...two orbits on the vertex set of Γ. We say the graph Γ is basic if it is G-basic for all arc-transitive subgroups G of Aut(Γ). All basic symmetric cubic graphs with solvable automorphism groups have been classified in Feng et al. (2015) 12. In this paper, a characterization of basic symmetric cubic graphs with non-solvable automorphism groups is given.
•In this paper, we use the occupancy method to show that n/6·GP(3,1) maximizes the number of independent sets in a claw-free cubic graph on n vertices, where GP(3,1) is the triangular-prism.•We also ...use the occupancy method to show that n/6·GP(3,1) maximizes the independence polynomial of a claw-free cubic graph on n vertices for λ∈(0,1541.
Let G be a graph. An independent set of G is a subset of vertices no two of which are connected by an edge. Denote by I(G) the set of all independent sets of G. The independence polynomial of G is I(G;λ)=∑I∈I(G)λ|I|.
The cartesian product C3□K2 is commonly called the triangular-prism, it is also a generalized Petersen graph on 6 vertices and denoted by GP(3,1). In this paper, we use the occupancy method to show that for any claw-free cubic graph G,|I(G)|≤|I(GP(3,1))||V(G)|/6,furthermore, for any λ∈(0,1541,I(G;λ)≤(I(GP(3,1);λ)|V(G)|/6,with equality holding in both cases if and only if G is a disjoint union of copies of GP(3,1).
2-Factors of cubic bipartite graphs Haghparast, Nastaran; Ozeki, Kenta
Discrete mathematics,
July 2021, 2021-07-00, Letnik:
344, Številka:
7
Journal Article
Recenzirano
For a positive integer k≥3, a {Cn:n≥k}-factor in a graph G is a spanning subgraph of G in which each component is a cycle of length at least k. Kano, Lee and Suzuki proved that every bipartite cubic ...graph contains a {Cn:n≥6}-factor. In this paper, we prove that every bipartite cubic graph G contains a {Cn:n≥8}-factor, provided that G satisfies some conditions related to 6-cycles.
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. Towards a proof of the ...conjecture that only finitely many finite simple groups have no cubic GRR, this paper shows that PSU3(q) has a cubic GRR if and only if q≥4. Indeed, for each q, we construct explicitly a cubic GRR of PSU3(q).
Cyclic (vertex and edge) connectivity is an important concept in graphs. While cyclic edge connectivity (cλ) has been studied for many years, the study at cyclic vertex connectivity (cκ) is still at ...the initial stage. And cκ seems to be more complicated than cλ. We have got a sufficient condition that ν(G)≥2g(k−1) for cκ≠∞. On the other hand, if ν(G)<2g(k−1), then we have cκ=∞, or cκ≤(k−2)g, or (k−2)g<cκ<∞. So characterizing all the k-regular graphs with (k−2)g<cκ<∞ is helpful to design an efficient algorithm for cκ. Hence, we characterize all 38 cubic graphs with g<cκ<∞ and prove that cκ=g+1.
Matching theory and Barnette's conjecture Gorsky, Maximilian; Steiner, Raphael; Wiederrecht, Sebastian
Discrete mathematics,
February 2023, 2023-02-00, Letnik:
346, Številka:
2
Journal Article
Recenzirano
Odprti dostop
Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to ...relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.
A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.
As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) 14. These allow us to check whether a graph we generated is a brace.
The 2-Decomposition Conjecture, equivalent to the 3-Decomposition Conjecture stated in 2011 by Hoffmann-Ostenhof, claims that every connected graph G with vertices of degree 2 and 3, and satisfying ...that G - E(C) is disconnected for every cycle C, admits a decomposition into a spanning tree and a matching. In this work we show that the 2-Decomposition Conjecture holds for graphs whose vertices of degree 3 induce a collection of cacti in which each vertex belongs to a cycle.
PDF
