A total [k]-coloring of a graph G is a mapping φ： V（G） U E（G） →{1, 2, ..., k} such that any two adjacent elements in V（G）UE（G） receive different colors. Let f（v） denote the sum of the colors of a vertex v...A total [k]-coloring of a graph G is a mapping φ： V（G） U E（G） →{1, 2, ..., k} such that any two adjacent elements in V（G）UE（G） receive different colors. Let f（v） denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total [k]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uv E E（G）, f（u） ≠ f（v）. By tt [G, Xsd（ J, we denote the smallest value k in such a coloring of G. Pilniak and Woniak conjectured X＇sd（G） 〈 A（G） ＋ 3 for any simple graph with maximum degree A（G）. This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds for Ka-minor free graphs. Furthermore, we show that if G is a Ka-minor flee graph with A（G） 〉 4, then ＂ Xnsd（G） 〈 A（G） ＋ 2. The bound A（G） ＋ 2 is sharp.展开更多
A decomposition of K_(n(g))∪Γ, the complete n-partite equipartite graph over gn vertices union a graph Γ(called the excess) that is a subgraph of K_(n(g)), into edge disjoint copies of a graph G is called a simple ...A decomposition of K_(n(g))∪Γ, the complete n-partite equipartite graph over gn vertices union a graph Γ(called the excess) that is a subgraph of K_(n(g)), into edge disjoint copies of a graph G is called a simple minimum group divisible covering of type g^n with G if Γ contains as few edges as possible. We examine all possible excesses for simple minimum group divisible(K_4-e)-coverings.Necessary and sufficient conditions are established for their existence.展开更多
A k-total coloring of a graph G is a mapping φ： V（G） U E（G） → {1, 2,..., k} such that no two adjacent or incident elements in V（G） U E（G） receive the same color. Let f（v） denote the sum of the color on th...A k-total coloring of a graph G is a mapping φ： V（G） U E（G） → {1, 2,..., k} such that no two adjacent or incident elements in V（G） U E（G） receive the same color. Let f（v） denote the sum of the color on the vertex v and the colors on all edges incident with v. We say that ~ is a k-neighbor sum distinguishing total coloring of G if f（u） ≠ f（v） for each edge uv C E（G）. Denote X＂ （G） the smallest value k in such a coloring of G. Pilgniak and Wo/niak conjectured that for any simple graph with maximum degree △（G）, X＂（G） ≤ 3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for Ka-minor free graph G with △（G） ≥ 5, X＂（G） = △（G） ＋ 1 if G contains no two adjacent A-vertices, otherwise, X＂（G） = △（G） ＋ 2.展开更多
Given a vertex v of a graph G the second order degree of v denoted as d2（v） is defined as the number of vertices at distance 2 from v. In this paper we address the following question： What axe the sufficient condit...Given a vertex v of a graph G the second order degree of v denoted as d2（v） is defined as the number of vertices at distance 2 from v. In this paper we address the following question： What axe the sufficient conditions for a graph to have a vertex v such that d2（v） ≥ d（v）, where d（v） denotes the degree of v？ Among other results, every graph of minimum degree exactly 2, except four graphs, is shown to have a vertex of second order degree as large as its own degree. Moreover, every K4^--free graph or every maximal planar graph is shown to have a vertex v such that d2（v） ≥ d（v）. Other sufficient conditions on graphs for guaranteeing this property axe also proved.展开更多
文摘A total [k]-coloring of a graph G is a mapping φ： V（G） U E（G） →{1, 2, ..., k} such that any two adjacent elements in V（G）UE（G） receive different colors. Let f（v） denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total [k]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uv E E（G）, f（u） ≠ f（v）. By tt [G, Xsd（ J, we denote the smallest value k in such a coloring of G. Pilniak and Woniak conjectured X＇sd（G） 〈 A（G） ＋ 3 for any simple graph with maximum degree A（G）. This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds for Ka-minor free graphs. Furthermore, we show that if G is a Ka-minor flee graph with A（G） 〉 4, then ＂ Xnsd（G） 〈 A（G） ＋ 2. The bound A（G） ＋ 2 is sharp.
基金Supported by NSFC(Grant Nos.11431003 and 11471032)Fundamental Research Funds for the Central Universities(Grant Nos.2016JBM071 and 2016JBZ012)
文摘A decomposition of K_(n(g))∪Γ, the complete n-partite equipartite graph over gn vertices union a graph Γ(called the excess) that is a subgraph of K_(n(g)), into edge disjoint copies of a graph G is called a simple minimum group divisible covering of type g^n with G if Γ contains as few edges as possible. We examine all possible excesses for simple minimum group divisible(K_4-e)-coverings.Necessary and sufficient conditions are established for their existence.
文摘A k-total coloring of a graph G is a mapping φ： V（G） U E（G） → {1, 2,..., k} such that no two adjacent or incident elements in V（G） U E（G） receive the same color. Let f（v） denote the sum of the color on the vertex v and the colors on all edges incident with v. We say that ~ is a k-neighbor sum distinguishing total coloring of G if f（u） ≠ f（v） for each edge uv C E（G）. Denote X＂ （G） the smallest value k in such a coloring of G. Pilgniak and Wo/niak conjectured that for any simple graph with maximum degree △（G）, X＂（G） ≤ 3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for Ka-minor free graph G with △（G） ≥ 5, X＂（G） = △（G） ＋ 1 if G contains no two adjacent A-vertices, otherwise, X＂（G） = △（G） ＋ 2.
基金Supported by the Ministry of Education and Science,Spainthe European Regional Development Fund (ERDF)under project MTM2008-06620-C03-02+2 种基金the Catalan Government under project 2009 SGR 1298CONACyTMxico under project 57371PAPIIT-UNAM IN104609-3
文摘Given a vertex v of a graph G the second order degree of v denoted as d2（v） is defined as the number of vertices at distance 2 from v. In this paper we address the following question： What axe the sufficient conditions for a graph to have a vertex v such that d2（v） ≥ d（v）, where d（v） denotes the degree of v？ Among other results, every graph of minimum degree exactly 2, except four graphs, is shown to have a vertex of second order degree as large as its own degree. Moreover, every K4^--free graph or every maximal planar graph is shown to have a vertex v such that d2（v） ≥ d（v）. Other sufficient conditions on graphs for guaranteeing this property axe also proved.
