The minimum number of total independent partition sets of
∪
of a graph
= (
) is called the
of
, denoted by
′(
). If the di erence between cardinalities of any two total independent sets is at most ...one, then the minimum number of total independent partition sets of
∪
is called the
, and is denoted by
).
In this paper we consider equitable total coloring of coronas of cubic graphs,
. It turns out that independently on the values of equitable total chromatic number of factors
and
, equitable total chromatic number of corona
◦
is equal to Δ(
◦
) + 1. Thereby, we confirm Total Coloring Conjecture (TCC), posed by Behzad in 1964, and Equitable Total Coloring Conjecture (ETCC), posed by Wang in 2002, for coronas of cubic graphs. As a direct consequence we get that all coronas of cubic graphs are of Type 1.
We investigate the bounds on algebraic connectivity of graphs subject to constraints on the number of edges, vertices, and topology. We show that the algebraic connectivity for any tree on n vertices ...and with maximum degree d is bounded above by 2(d−2)1n+O(lnnn2). We then investigate upper bounds on algebraic connectivity for cubic graphs. We show that algebraic connectivity of a cubic graph of girth g is bounded above by 3−23/2cos(π/⌊g/2⌋), which is an improvement over the bound found by Nilli 34. Finally, we propose several conjectures and open questions.
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in ...the graph. We prove that the problem of finding a PDS of maximum size is APX-hard on split graphs, and NP-hard on bipartite graphs. We also show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs. Nevertheless, we present a simple polynomial-time (2−2Δ+1)-approximation algorithm for the problem, where Δ is the maximum degree of the graph. Finally, we show that all Hamiltonian cubic graphs with n vertices (except two) have a PDS of size ⌊2n+13⌋, which we prove to be an upper bound on the size of a PDS in cubic graphs.
Assume that G models a facility with a possible “intruder” (or a multiprocessor network with a possible malfunctioning processor). We consider placing (the minimum number of) detectors at vertices in ...G to precisely determine the location of the intruder. Various distinguishing set parameters have been defined based on the functionality of the detector. We characterize several types of fault-tolerant detectors identified for the open-locating-dominating sets and determine the bounds on the minimum size of these sets for cubic graphs.
The adjacent vertex-distinguishing edge-coloring of a graph $ G $ is a proper edge-coloring of $ G $ such that each pair of adjacent vetices receives a distinct set of colors. The minimum number of ...colors required in an adjacent vertex-distinguishing edge-coloring of $ G $ is called the adjacent vertex-distinguishing chromatic index. In this paper, we determine the adjacent vertex distinguishing chromatic indices of cubic Halin graphs whose characteristic trees are caterpillars.
Let $ G $ be a graph. A dissociation set of $ G $ is a subset of vertices that induces a subgraph with vertex degree at most 1. The dissociation polynomial of $ G $ is $ D_{G}(\lambda) = \sum_{D \in ...\mathcal{D}(G)} \lambda^{|D|} $, where $ \mathcal{D}(G) $ is the set of all dissociation sets of $ G $. In this paper, we prove that for any cubic graph $ G $ and any $ \lambda \in(0, 1 $,
<disp-formula> <tex-math id="FE1"> \begin{document}$ \frac{1}{|V(G)|} \ln D_{G}(\lambda) \leq \frac{1}{4} \ln D_{K_4}(\lambda) $\end{document} </tex-math></disp-formula>
with equality if and only if $ G $ is a disjoint union of copies of the complete graph $ K_{4} $. When $ \lambda = 1 $, the value of $ D_G(\lambda) $ is exactly the number of dissociation sets of $ G $. Hence, for any cubic graph $ G $ on $ n $ vertices, $ |\mathcal{D}(G)|\leq|\mathcal{D}(K_4)|^{n/4} = 11^{n/4}. $
We construct an infinite family of counterexamples to Thomassen’s conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue ...subgraph has maximum degree at most 1 and the red subgraph minimum degree at least 1 and contains no path on 4 vertices.
A 3-star is a complete bipartite graph
K
1
,
3
. A 3-star packing of a graph
G
is a collection of vertex-disjoint subgraphs of
G
in which each subgraph is a 3-star. The maximum 3-star packing problem ...is to find a 3-star packing of a given graph with the maximum number of 3-stars. A 2
-independent set
of a graph
G
is a subset
S
of
V
(
G
) such that for each pair of vertices
u
,
v
∈
S
, paths between
u
and
v
are all of length at least 3. In cubic graphs, the maximum 3-star packing problem is equivalent to the maximum 2-independent set problem. The maximum 2-independent set problem was proved to be NP-hard on cubic graphs (Kong and Zhao in Congressus Numerantium 143:65–80, 2000), and the best approximation algorithm of maximum 2-independent set problem for cubic graphs has approximation ratio
8
15
(Miyano et al. in WALCOM 2017, Proceedings, pp 228–240). In this paper, we first prove that the maximum 3-star packing problem is NP-hard in claw-free cubic graphs and then design a linear-time algorithm which can find a 3-star packing of a connected claw-free cubic graph
G
covering at least
3
v
(
G
)
-
8
4
vertices, where
v
(
G
) denotes the number of vertices of
G
.
Automated discovery of angle theorems Todd, Philip
Annals of mathematics and artificial intelligence,
12/2023, Letnik:
91, Številka:
6
Journal Article
Recenzirano
Odprti dostop
We consider geometry theorems whose premises and statement comprise a set of bisector conditions. Each premise and the statement can be represented as the rows of a “bisector matrix”: one with three ...non zero elements per row, one element with value -2 and the others with value 1. The existence of a theorem corresponds to rank deficiency in this matrix. Our method of theorem discovery starts with identification of rank deficient bisector matrices. Some such matrices can be represented as graphs whose vertices correspond to matrix rows and whose edges correspond to matrix columns. We show that if a bisector matrix which can be represented as a graph is rank deficient, then the graph is bicubic. We give an algorithm for finding the rank deficient matrices for a Hamiltonian bicubic graph, and report on the results for graphs with 6,8,10 and 12 vertices. We discuss a method of deriving rank deficient bisector matrices with more than 2 non-zero elements. We extend the work to matrices containing rows corresponding to angle trisectors.
Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let Ei be the set of edges contained in precisely i members of the k 1‐factors. Let μk(G) be the smallest |E0| over all lists ...of k 1‐factors of G. We study lists by three 1‐factors, and call GE0∪E2∪E3 with |E0|=μ3(G) a μ3(G)‐core of G. If G is not 3‐edge‐colorable, then μ3(G)≥3. In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if μ3(G)≠0, then 2μ3(G) is an upper bound for the girth of G. We show that μ3(G) bounds the oddness ω(G) of G as well. We prove that ω(G)≤23μ3(G). If ω(G)=23μ3(G), then every μ3(G)‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with ω(G)=23μ3(G). On the other hand, the difference between ω(G) and 23μ3(G) can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer k≥3, there exists a bridgeless cubic graph G such that μ3(G)=k.
PDF
