Cycle Multiplicity of Total Graph of Complete Bipartite Graph

Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].

Perfect 1-k Matchings of Bipartite Graphs

Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.

On the (Δ + 2)-Total-Colorability of Planar Graphs with 7-Cycles Containing at Most Two Chords

The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.

The Edge Connectivities of Total P_(k)-graphs

The P_(k)-path graph P_(k)(G)corresponding to a graph G has for vertices the set of all paths of length k in G.Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path of length k-1 in G,and their union forms either a cycle or a path of length k+1.Let Ek={(v,p),p E V(P_(k)(G)),v is an end vertex of p in G},we define total P_(k)-graphs T_(k)(G)as Yk(G)=(V(G)UV(P_(k)(G)),E(G)U E(PI(G))U Ek).In this note,we introduce total P,-graphs Th(G)and study their edge connectivity,as the generaliza-tion of total graphs.

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K 7,n when7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.

ON THE TOTAL COLORING OF GRAPH G ∨H

The total chromatic number XT(G) of graph G is the least number of colorsassigned to VE(G) such that no adjacent or incident elements receive the same color.Gived graphs G1,G2, the join of G1 and G2, denoted by G1∨G2, is a graph G, V(G) =V(GI)∪V(G2) and E(G) = E(G1)∪E(G2) ∪{uv | u∈(G1), v ∈ V(G2)}. In this paper, it's proved that if v(G) = v(H), both Gc and Hc contain perfect matching and one of the followings holds: (i)Δ(G) =Δ(H) and there exist edge e∈ E(G), e' E E(H)such that both G-e and H-e' are of Class l; (ii)Δ(G)<Δ(H) and there exixst an edge e ∈E(H) such that H-e is of Class 1, then, the total coloring conjecture is true for graph G ∨H.

Minus total k-subdomination in graphs

Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.

Total Domination number of Generalized Petersen Graphs

Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.

On the Total Domination Number of Graphs with Minimum Degree at Least Three

Let G be a simple graph with no isolated vertices. A set S of vertices of G is a total dominating set if every vertex of G is adjacent to some vertex in S . The total domination number of G , denoted by γ t (G) , is the minimum cardinality of a total dominating set of G . It is shown that if G is a graph of order n with minimum degree at least 3, then γ t (G)≤n/2 . Thus a conjecture of Favaron, Henning, Mynhart and Puech is settled in the affirmative.

Signed total domination in nearly regular graphs

A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.

A Remark on the Characterization of Triangulated Graphs

In this study, we consider the problem of triangulated graphs. Precisely we give a necessary and sufficient condition for a graph to be triangulated. This gives an alternative characterization of triangulated graphs. Our method is based on the so-called perfectly nested sequences.

Vertex-distinguishing VE-total Colorings of Cycles and Complete Graphs

Let G be a simple graph of order at least 2.A VE-total-coloring using k colors of a graph G is a mapping f from V (G) E(G) into {1,2,···,k} such that no edge receives the same color as one of its endpoints.Let C(u)={f(u)} {f(uv) | uv ∈ E(G)} be the color-set of u.If C(u)=C(v) for any two vertices u and v of V (G),then f is called a k-vertex-distinguishing VE-total coloring of G or a k-VDVET coloring of G for short.The minimum number of colors required for a VDVET coloring of G is denoted by χ ve vt (G) and it is called the VDVET chromatic number of G.In this paper we get cycle C n,path P n and complete graph K n of their VDVET chromatic numbers and propose a related conjecture.

Cyclically Interval Total Colorings of Cycles and Middle Graphs of Cycles

A total coloring of a graph G is a functionsuch that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. A k-interval is a set of k consecutive integers. A cyclically interval total t-coloring of a graph G is a total coloring a of G with colors 1,2,...,t, such that at least one vertex or edge of G is colored by i,i=1,2,...,t, and for any, the set is a -interval, or is a -interval, where dG(x) is the degree of the vertex x in G. In this paper, we study the cyclically interval total colorings of cycles and middle graphs of cycles.

Adjacent Vertex-distinguishing E-total Coloring on Some Join Graphs Cm V Gn

Let G(V, E) be a simple connected graph and k be positive integers. A mapping f from V∪E to {1, 2, ··· , k} is called an adjacent vertex-distinguishing E-total coloring of G(abbreviated to k-AVDETC), if for uv ∈ E(G), we have f(u) ≠ f(v), f(u) ≠ f(uv), f(v) ≠ f(uv), C(u) ≠C(v), where C(u) = {f(u)}∪{f(uv)|uv ∈ E(G)}. The least number of k colors required for which G admits a k-coloring is called the adjacent vertex-distinguishing E-total chromatic number of G is denoted by x^e_(at) (G). In this paper, the adjacent vertexdistinguishing E-total colorings of some join graphs C_m∨G_n are obtained, where G_n is one of a star S_n , a fan F_n , a wheel W_n and a complete graph K_n . As a consequence, the adjacent vertex-distinguishing E-total chromatic numbers of C_m∨G_n are confirmed.

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.

The Total Irredundance Numbers on Graphs

This paper discusses the total irredundance relations between the graph G and its clone-contraction graph H, that is, let H be the clone-contraction graph of G and v1,v2,...,vk be all contraction vertices ofH. IfS is a maximal total irredundant set of H such that A = S ∩ {V1,V2,…,Vk} contains as few vertices as possible, then S＇= S-A is the maximal total irredundant set of G. Furthermore, we obtain the bound of the total irredundance A（G） number： irt ≤△（G）/2△（G）＋1 n, which n is the order of graph G, and △（G） is maximum degree in G.

The Number of Minimum Roman and Minimum Total Dominating Sets for Some Chessboard Graphs

In this paper, both the roman domination number and the number of minimum roman dominating sets are found for any rectangular rook’s graph. In a similar fashion, the roman domination number and the number of minimum roman dominating sets are found on the square bishop’s graph for odd board sizes. Also found are the number of minimum total dominating sets associated with the light-colored squares when n?&#8801;1(mod12)? (with n>1), and same for the dark-colored squares when n?&#8801;7(mod12) .

Reverse Total Signed Vertex Domination in Graphs

Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every , the sum of function values over v and the elements incident to v is less than zero. In this paper, we present some upper bounds of reverse total signed vertex domination number of a graph and the exact values of reverse total signed vertex domination number of circles, paths and stars are given.

Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies

In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, &#8230;, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,&#8230;, Gk?by identifying the vertices u (respectively, v) and w1, w2,&#8230;, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n&#8805;211.