Partial cubes are the graphs which can be embedded into hypercubes. The cube polynomial of a graph
G is a counting polynomial of induced hypercubes of
G, which is defined as
C
(
G
,
x
)
≔
∑
i
⩾
0
α
i
...(
G
)
x
i, where
α
i
(
G
) is the number of induced
i‐cubes (hypercubes of dimension
i) of
G. The clique polynomial of
G is defined as
C
l
(
G
,
x
)
≔
∑
i
⩾
0
a
i
(
G
)
x
i, where
a
i
(
G
) (
i
⩾
1) is the number of
i‐cliques in
G and
a
0
(
G
)
=
1. Equivalently,
C
l
(
G
,
x
) is exactly the independence polynomial of the complement
G
¯ of
G. The crossing graph
G
# of a partial cube
G is the graph whose vertices are corresponding to the
Θ‐classes of
G, and two
Θ‐classes are adjacent in
G
# if and only if they cross in
G. In the present paper, we prove that for a partial cube
G,
C
(
G
,
x
)
⩽
C
l
(
G
#
,
x
+
1
) and the equality holds if and only if
G is a median graph. Since every graph can be represented as the crossing graph of a median graph, the above necessary‐and‐sufficient result shows that the study on the cube polynomials of median graphs can be transformed to the one on the clique polynomials of general graphs (equivalently, on the independence polynomials of their complements). In addition, we disprove the conjecture that the cube polynomials of median graphs are unimodal.
A graph is called a partial cube if it can be embedded into a hypercube isometrically. In this paper, we study a class of Cayley graphs—Cayley graphs generated by transpositions—and show that a ...Cayley graph
Γ generated by transpositions is a partial cube if and only if
Γ is a bubble sort graph. This result enhances a result of Alahmadi et al. in 2016:
BSn is a partial cube. As a corollary, we give the analytical expressions of the Wiener indices of bubble sort graphs.
To compare the short-term clinical effect and to assess the influencial factors of immediate implant placement and delayed implant placement around single-tooth implant in the aesthetic area.
A total ...of 114 patients requiring a single-tooth implant in the aesthetic area were reviewed at Center for Implant Dentistry of Stomatological Hospital of China Medical University. They were divided into immediate implant group and delayed implant group. The patients were followed up for 1 year after upper structure rehabilitation, and the pink esthetic score and the marginal bone absorption around the implants were measured. Statistical analysis was performed using SPSS 17.0 software package.
After 1 year of upper structure rehabilitation, 114 implants were stable and the marginal bone absorption around the implants of the immediate implant group was (0.36±0.39) mm,significantly smaller than the delayed implant group (0.79±0.67)mm, P<0.001. The difference in PES score between the two groups were not statistically sign
Identifying molecular subtypes of colorectal cancer (CRC) may allow for more rational, patient-specific treatment. Various studies have identified molecular subtypes for CRC using gene expression ...data, but they are inconsistent and further research is necessary. From a methodological point of view, a progressive approach is needed to identify molecular subtypes in human colon cancer using gene expression data. We propose an approach to identify the molecular subtypes of colon cancer that integrates denoising by the Bayesian robust principal component analysis (BRPCA) algorithm, hierarchical clustering by the directed bubble hierarchical tree (DBHT) algorithm, and feature gene selection by an improved differential evolution based feature selection method (DEFS
) algorithm. In this approach, the normal samples being completely and exclusively clustered into one class is considered to be the standard of reasonable clustering subtypes, and the feature selection pays attention to imbalances of samples among subtypes. With this approach, we identified the molecular subtypes of colon cancer on the mRNA gene expression dataset of 153 colon cancer samples and 19 normal control samples of the Cancer Genome Atlas (TCGA) project. The colon cancer was clustered into 7 subtypes with 44 feature genes. Our approach could identify finer subtypes of colon cancer with fewer feature genes than the other two recent studies and exhibits a generic methodology that might be applied to identify the subtypes of other cancers.
A connected graph of order at least 2k+2 is k-extendable for a non-negative integer k if it contains a perfect matching and every matching of size k can be extended to a perfect matching. The ...extendability number of the graph is the maximum k such that the graph is k-extendable. In this paper, we prove that, for a Cayley graph Γ of a symmetric group with respect to a generating set of size m consisting of transpositions, the extendability number of Γ is m−1.
Let Γ be a simple connected graph with vertex set V(Γ). The eccentric distance sum (EDS for short) of Γ is defined as ξd(Γ)=∑v∈V(Γ)εΓ(v)DΓ(v), where ɛΓ(v) is the eccentricity of a vertex v and DΓ(v) ...is the sum of all distances from v to other vertices. In the paper Li and Wu 11, the strict upper bound on ξd(Γ) among the k-connected graphs Γ with an integer k even were given, and proposed an open question: the corresponding problem on k-connected graphs with k odd. In this paper, first, we divide cubic transitive graphs into two cases: super-connectedness and non-super-connectedness, and characterized non-super-connected cubic transitive graphs, filling the gaps in this field. Then, by using the characterization, we show the upper bound on EDS among (3-connected) cubic transitive graphs of order n and characterize the extremal graphs: the ladders when n≡0(mod4) and the ladders or the Möbius ladders when n≡2(mod4). Finally, we conclude the paper with conjectures about the upper bound on EDS of k-connected graphs with odd integer k ≥ 3.
Let S be a set of transpositions that generates the symmetric group Sn on n={1,2,…,n}, where n⩾3. The corresponding Cayley graph is denoted by Cay(Sn,S). The transposition generating graph T(S) of S ...is a graph with vertex set n and with vertices s and t being adjacent in T(S) whenever (st)∈S. A graph Γ is called induced matching extendable (shortly, IM-extendable) if every induced matching of Γ is included in a perfect matching of Γ. In this paper, we proved that Cay(Sn,S) is IM-extendable if and only if T(S) has true twins, where true twins are defined as a pair of vertices such that they have the same closed neighbourhood in T(S). In addition, we give a linear algorithm for checking true twins in T(S).
Abstract Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a regular ...partial cube is a hypercube (resp., a Doubled Odd graph, an even cycle of length where ) if and only if all its convex cycles are 4‐cycles (resp., 6‐cycles, ‐cycles). In particular, the partial cubes whose all convex cycles are 4‐cycles are equivalent to almost‐median graphs. Therefore, we conclude that regular almost‐median graphs are exactly hypercubes, which generalizes the result by Mulder—regular median graphs are hypercubes.
Let Γ be a graph with its automorphism group G and s(⩾0) an integer. We call a vertex sequence (v0,v1,…,vs) of length s+1 of Γ an s-arc if two consecutive vertices are adjacent and vi≠vi+2 for ...0⩽i⩽s−2. Γ is called s-arc-transitive if G acts on its s-arc set transitively. If Γ is s-arc-transitive, but not (s+1)-arc-transitive, we call it an s-transitive graph. Γ is a partial cube if Γ can be embedded into a hypercube isometrically. In this paper, we characterized non-trivial regular 2-arc-transitive partial cubes as three classes of graphs: hypercubes, doubled Odd graphs and even cycles. As a corollary, we prove that there exist no regular s-transitive partial cubes for s⩾4 and characterized regular s-transitive partial cubes for s=2 or 3.
Uniform and spherical Li(Ni1/3Co1/3Mn1/3)O(2-delta)Fdelta powders were synthesized via NH3 and F- coordination hydroxide co-precipitation. The effect of F- coordination agent on the morphology, ...structure and electrochemical properties of the Li(Ni1/3Co1/3Mn1/3)O(2-delta)Fdelta were studied. The morphology, size, and distribution of (Ni1/3Co1/3Mn1/3)(OH)(2-delta)Fdelta particle diameter were improved in a shorter reaction time through the addition of F-. The study suggested that the added F improves the layered characteristics of the lattice and the cyclic performance of Li(Ni1/3Co1/3Mn1/3)O2 in the voltage range of 2.8-4.6V. The initial capacity of the Li(Ni1/3Co1/3Mn1/3)O1.96F0.04 was 178mAhg-1, the maximum capacity was 186mAhg-1 and the capacity after 50 cycles was 179mAhg-1 in the voltage range of 2.8-4.6V.