39744832
On signed edge domination numbers of graphs
Abstract Given a graph G=(V,E) , if e=uv∈E , then the closed edge-neighbourhood of e is denoted by N[e]={u′v′∈E|u′=u or v′=v} . A function f : E→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑ e′∈N[e] f(e′)⩾1 for every e∈E . The signed edge domination number γ s ′(G) of G is defined as γ s ′(G)= min {∑ e∈E f(e) | f is an SEDF of G} . Let Ψ(m)= min {γ s ′(H)|H is a graph with |E(H)|=m} . In this paper, we determine the exact value of Ψ(m) for each positive integer m . That is: Ψ(m)=2 1 3 24m+25 +6m+5 6 −m, where ⌈x⌉ denotes the ceiling of x . In addition, we also characterize all connected graphs G with γ s ′(G)=|E(G)| .
24660543
A note on the lower bounds of signed domination number of a graph
Abstract Let G = (V, E) be a graph. For a function f : V → {−1, 1}, the weight of f is w(f) = Σv ∈ V f(v). For a vertex v in V, we define f[v] = Σu∈N[v] f(u). A signed dominating function of G is a function f : V → {−1, 1} such that f[v] ⩾ 1 for all v ∈ V. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. A signed dominating function of a weight γs(G) we call a γs-function of G. In this paper, we study the signed domination problem of general graph, and obtain some lower bounds of the signed domination number of a graph, and show that these lower bounds are sharp, and extend a result in Dunbar et al. (1995).
31788400
Extremal graphs for inequalities involving domination parameters
Abstract A characterization of n-vertex isolate-free connected graphs G whose domination number γ ( G ) satisfies γ(G)=⌊n/2⌋ is obtained. This result enables us to obtain extremal graphs of inequalities which bound the sum of two domination parameters in isolate-free graphs.
29802636
Two classes of edge domination in graphs
Let γ's(G) (γ'l(G), resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that γ's(G) ≤ ⌊11/6n - 1⌋ and γ's(G) ≤ 2n - 4 hold for any graph G of order n (n ≥ 4), and pose several open problems and conjectures.
37647794
On 3-colorable plane graphs without 5- and 7-cycles
In this note, it is proved that every plane graph without 5- and 7-cycles and without adjacent triangles is 3-colorable. This improves the result of [O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B 93 (2005) 303-311], and offers a partial solution for a conjecture of Borodin and Raspaud [O.V. Borodin, A. Raspaud, A sufficient condition for planar graphs to be 3-colorable, J. Combin. Theory Ser. B 88 (2003) 17-27].
30641096
On the fixed edge of planar graphs with minimum degree five
Abstract An edge e of a finite and simple graph G is called a fixed edge of G if G - e + e ′ ≅ G implies e ′ = e . In this paper, we show that planar graphs with minimum degree 5 contain fixed edges, from which we prove that a class of planar graphs with minimum degree one is edge reconstructible.
20988039
Two conjectures equivalent to the perfect graph conjecture
Abstract In this note, we study the graphs with the property that each of their induced subgraphs has circular clique number (defined in Section 2) the same as its clique number, prove that a graph satisfies such a property if and only if neither itself nor its complement contains an induced subgraph isomorphic to an odd cycle of length at least five, and then give two conjectures which are equivalent to the perfect graph conjecture.
16379968
On Structure of Some Plane Graphs with Application to Choosability
A graph G=(V, E) is (x, y)-choosable for integers xy?1 if for any given family {A(v)?v?V} of sets A(v) of cardinality x, there exists a collection {B(v)?v?V} of subsets B(v)?A(v) of cardinality y such that B(u)?B(v)=? whenever uv?E(G). In this paper, structures of some plane graphs, including plane graphs with minimum degree 4, are studied. Using these results, we may show that if G is free of k-cycles for some k?{3, 4, 5, 6}, or if any two triangles in G have distance at least 2, then G is (4m, m)-choosable for all nonnegative integers m. When m=1, (4m, m)-choosable is simply 4-choosable. So these conditions are also sufficient for a plane graph to be 4-choosable.
14675818
A physically based method for triangulated surface flattening
This paper introduces a new method of generating 2D flat patterns from a 3D triangulated surface by opening the bending configuration of each winged triangle pair. The flattening can be divided into four steps. First, a 3D triangulated surface is modeled with a mass-spring system that simulates the surface deformation during the flattening. Second, an unwrapping force field is built to drive the mass-spring system to a developable configuration through the numerical integration. Third, a velocity redistribution procedure is initiated to average velocity variances among the particles. Finally, the mass-spring system is forced to collide with a plane, and the final 2D pattern is generated after all the winged triangle pairs are spread onto the colliding plane. To retain the size and area of the original 3D surface, a strain control mechanism is introduced to keep the springs from over-elongation or over-shrinkage at each time step.